Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
K-edge-connected graph
Summary
In graph theory, a connected graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.
The edge-connectivity of a graph is the largest k for which the graph is k-edge-connected.
Edge connectivity and the enumeration of k-edge-connected graphs was studied by Camille Jordan in 1869.
Let be an arbitrary graph.
If the subgraph is connected for all where , then G is said to be k-edge-connected.
The edge connectivity of is the maximum value k such that G is k-edge-connected. The smallest set X whose removal disconnects G is a minimum cut in G.
The edge connectivity version of Menger's theorem provides an alternative and equivalent characterization, in terms of edge-disjoint paths in the graph. If and only if every two vertices of G form the endpoints of k paths, no two of which share an edge with each other, then G is k-edge-connected. In one direction this is easy: if a system of paths like this exists, then every set X of fewer than k edges is disjoint from at least one of the paths, and the pair of vertices remains connected to each other even after X is deleted. In the other direction, the existence of a system of paths for each pair of vertices in a graph that cannot be disconnected by the removal of few edges can be proven using the max-flow min-cut theorem from the theory of network flows.
Minimum vertex degree gives a trivial upper bound on edge-connectivity. That is, if a graph is k-edge-connected then it is necessary that k ≤ δ(G), where δ(G) is the minimum degree of any vertex v ∈ V. Obviously, deleting all edges incident to a vertex, v, would then disconnect v from the graph.
Edge connectivity is the dual concept to girth, the length of the shortest cycle in a graph, in the sense that the girth of a planar graph is the edge connectivity of its dual graph, and vice versa. These concepts are unified in matroid theory by the girth of a matroid, the size of the smallest dependent set in the matroid. For a graphic matroid, the matroid girth equals the girth of the underlying graph, while for a co-graphic matroid it equals the edge connectivity.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.