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 thatfor
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.
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
- If G is a complete graph
then
