4.2. Edge-cut and edge-connectivity

An edge-cut in a graph G is a set X of edges of G such that is disconnected. An edge-cut X is minimal if no proper subset of X is also an edge-cut.

A graph G is k-edge-connected if it has at least two vertices and no set of at most edges separates G.

The edge-connectivity, , of a graph G is the minimum cardinality of an edge-cut of G if G is nontrivial, and .

Statement 4.2. If X is a minimal edge-cut of a connected graph G, then contains exactly two components.

Examples:

  • A graph G is 2-edge-connected iff it is connected, has at least two vertices and contains no bridge.
  • iff G is disconnected or trivial.
  • iff G is connected and contains a bridge.

It is often easy  to determine  the connectivity of a given graph. If then

From the above examples one can think that for every graph .The following counterexample shows that this conjecture is not true.

 

Figure 4.1. A graph for which and .

Theorem 4.3. (R. A. Brualdi, J. Csima, 1991): Let G be a connected graph of order that is not complete. For each edge-cut X there exists a vertex-cut W of G such that .

Proof. W.l.o.g. we can suppose that X is a minimal edge-cut of G. Then is disconnected, which contains exactly two components, say and with order and , respectively. Then . We have two cases:

  • Every vertex of is adjacent to every vertex of in G. Then . Since , it follows that and so . Therefore G is not complete, it contains two non-adjacent vertices u and v. Then is a vertex-cut of cardinality , and so .
  • There are vertices u,v such that and they are not adjacent in G. For each edge , we select a vertex for W in the following way: If u is incident with e, then choose the other vertex (in ) incident with eW. Otherwise, select for W the vertex that is incident with e and belongs to . Now . Since , and contains no path, so W is a vertex-cut.
    for

Theorem 4.4. (H. Whitney, 1932, Connectivity Theorem): If G is a non-trivial graph then

Proof.

  • If we delete all the edges incident with a vertex, the graph becomes disconnected, so the second inequality holds.
  • Let us see the other inequality:
    • If G is a complete graph then .
    • Suppose G is not complete and . Let be an edge-cut. Then - by the Theorem 4.3. - there exists a vertex-cut U such that . Thus