Edge and vertex connectivity

5.1 Edge and vertex connectivity

Denition 5.1 Edge cut of a connected graph is called a subset of edges whose removal renders the graph disconnected.

Denition 5.2 Vertex cut of a connected graph is called a subset of vertices, whose removal renders the graph disconnected.

Denition 5.3 The edge connectivity of a connected graph G, which has at least two vertices is called the smallest power of his edge cut. The edge connectivity of a graph G is denoted by λ(G).

Denition 5.4 The vertex connectivity of a connected graph G, which has more than two vertices is called the smallest power of his vertex cut. The vertex connectivity of a graph G is denoted by κ(G). We say that undirected graph G is k-edge connected, if λ(G) > k. Similary, we say that the graph is k-vertex connected or simply that is k-connected if κ(G) > k. The reason that we can say about the k-connected graph, not to adding that it's about vertex connectivity is that if the graph is k-vertex connected then it's also k-edge connected. This follows from following simple Theorem:

Theorem 5.1 For any connected graph G, which has more than two vertices, there is relationship κ(G) 6 λ(G).

Proof: Choose in G any edge cut of minimum power. He therefore has exactly λ(G) edges. Next, create a set of incident vertices with these edges and for each pair of adjacent vertices remove one element of the pairs. Creates a vertex cut of graph with power of not more than λ(G).

Denition 5.5 Edge cut two dierent vertices v and w of a connected graph G is called this subset of the edges of this graph that every path connecting the vertices v and w contains the edge of that subset.

1

Denition 5.6 Vertex cut the vertices v and w, v 6= w, of a connected graph G is called this subset of the vertices of the dierent vertices of this graph from them that every path connecting the vertices v and w contains the vertex of that subset.

Example 5.2 Consider the undirected graph shown in Figure 5.2, in which distinguishes two vertices v and w. The edge cuts of the vertices v and w are for example the following subsets of the edges: {{a, d}, {b, d}, {e, h}, {e, i}} or {{v, a}, {v, b}, {v, c}}. Examples of vertex cuts of the vertices v and w are the following vertices subsets: {d, e}, {a, b, h, i}.

Theorem 5.2 (The edge connectivity version of Menger's theorem) The largest number of edge disjoint paths which contain two dierent vertices v and w of a connected graph is equal to the minimum number of edges in edge cut for vertices v and w.

Theorem 5.3 (The vertex connectivity version of Menger's theorem) The largest number of vertex disjoint paths which contain two dierent independent vertices v and w of a connected graph is equal to the minimum number of vertices in vertex cut for vertices v and w. Simple conclusions from Theorem 5.2 and 5.3 are the following facts:

The conclusion 5.1 A graph is k-edge-connected if and only if each two dierent vertices are connected at least k of edge dosjoint paths.

The conclusion 5.2 A graph with at least k + 1 vertices is k-connected if and only if each two dierent vertices are conncted at least k of vertex dosjoint paths. So let's consider the directed graph D = (V, A) and let S and T denote any subsets of his vertices. We do not exclude that S ∩ T 6= ∅.

Denition 5.7 The elementary path P = (v1 , ..., vk ) in the directed graph D = (V, A) is called S − T path for S, T ⊆ V , if V (P ) ∩ T = {vk }.

2

The vertices of the set V (P ) \ ({v1 } ∪ {vk }) is called internal vertex of the set S − T of the path P = (v1 , ..., vk ). Recall, that a single vertex is treated as a path in a directed graph D. Therefore path P = (v) is S − T path in D = (V, A) for any v ∈ S ∩ T and set of internal vertices of this path is empty.

Denition 5.8 Set Z ⊆ V is called S −T separator of the directed graph D = (V, A) for S, T ⊆ V , if a directed graph created from the graph G after removing vertices belonging to the set Z , does not contain S − T path. The power of the S − T separator is called cardinality of the set of vertices forming it. Let's note that power of the S − T seperator can't be less than the cardinality of sets S ∩ T , because every S − T separator must contain all vertices that belong to the common part of the sets S, T.

Denition 5.9 Subgraph Q = (VQ , AQ ) of the directed graph D = (V, A), which any connected component is S − T path, where S, T ⊆ V is called S − T connector of the graph D. The number connected components of the S − T connector is called of his power. Let's note that any directed empty graph Q = (W, ∅) is S − T connector of the directed graph D = (V, A) for any W ⊆ S ∩ T . The power of that S − T connector is equal to the cardinality of vertices set W .

3