# k-edge-connected graph

In graph theory, a 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.

## Formal definition

Let $G = (V, E)$ be an arbitrary graph. If subgraph $G' = (V, E \setminus X)$ is connected for all $X \subseteq E$ where $|X| < k$, then G is k-edge-connected.

## Relation to minimum vertex degree

Minimum vertex degree gives a trivial upper bound on edge-connectivity. That is, if a graph $G = (V, E)$ 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 n is the number of vertices in the graph, this simple algorithm would perform $O(n^2)$ iterations of the Maximum flow problem, which can be solved in $O(n^3)$ time. Hence the complexity of the simple algorithm described above is $O(n^5)$ in total.

An improved algorithm will solve the maximum flow problem for every pair (u,v) where u is arbitrarily fixed while v varies over all vertices. This reduces the complexity to $O(n^4)$ and is sound since, if a cut of capacity less than k exists, it is bound to separate u from some other vertex. It can be further improved by an algorithm of Gabow that runs in worst case $O(n^3)$ time. [1]

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$.[2]