k-edge-connected graph

In graph theory, a graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.

Formal definition

Let G = (E,V) be an arbitrary graph. If G' = (E \ X,V) is connected for all X ⊆ E where |X| < k, then G is k-edge-connected. Trivially, a graph that is k-edge-connected is also (k−1)-edge-connected.

Relation to minimum vertex degree

Minimum vertex degree gives a trivial upper bound on edge-connectivity. That is, if a graph G = (E,V) 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.

Computational aspects

There is a polynomial-time algorithm to determine the largest k for which a graph G is k-edge-connected. A simple algorithm would, for every pair (u,v), determine the maximum flow from u to v with the capacity of all edges in G set to 1 for both directions. A graph is k-edge-connected if and only if the maximum flow from u to v is at least k for any pair (u,v), so k is the least u-v-flow among all (u,v).

If V is the number of vertices in the graph, this simple algorithm would perform $O(V^2)$ iterations of the Maximum flow problem, which can be solved in $O(V^3)$ time. Hence the complexity of the simple algorithm described above is $O(V^5)$ in total.

A related problem: finding the minimum k-edge-connected subgraph of G (that is: select as few as possible edges in G that your selection is k-edge-connected) is NP-hard for $k\geq 2$.

See also

• k-vertex-connected graph
• Connectivity (graph theory)
• Menger's theorem
• Robbins theorem