Applied Graph Theory: Connectivity

This article covers the basic definitions of connectivity, vertex cut, and edge-connectivity. It also explains 2-connected graphs and k-connected and k-edge-connected graphs. Theorems such as the Expansion Lemma and Whitney's Theorem are also discussed. The article concludes with the characterization of 2-connected graphs. The subject is Applied Graph Theory with course code CS4L006. The author is Joy Mukherjee from the School of Electrical Sciences, Computer Science and Engineering at the Indian Institute of Technology Bhubaneswar.

CS4L006 :Applied Graph Theory
Connectivity
Joy Mukherjee
Schoolof ElectricalSciences
Computer Science and Engineering
Indian Institute of Technology Bhubaneswar
1 / 39

Outline
1 Basic Definitions
2 Connectivity
3 Edge-Connectivity
4 2-Connected Graphs
5 k-connected and k-edge-connected graphs
2 / 39

Outline
1 Basic Definitions
2 Connectivity
3 Edge-Connectivity
4 2-Connected Graphs
5 k-connected and k-edge-connected graphs
3 / 39

Vertex Cut & Connectivity
Definition
Separating Set / Vertex Cut (VC (G )) = {S|S ⊆ V (G ) ∧ G \ S has
than one component}.
Definition
The conectivity of (G), written as κ(G ), is the minimum size of a
set S such that V \ S is disconnected or has only one vertex.
Definition
A graph is k-connected if its connectivity is atleast k.A k-Connected
Graph (other than a complete graph) is a graph where every VC
least k vertices i.e.deletion of any (k − 1) vertices can not make it
disconnected.
4 / 39

Vertex Cut & Connectivity
κ(Kn) = n − 1.κ(K1) = 0.
κ(Km,n) = min{m, n}.
κ(Qk) = k.
κ(disconnected graph with more than one vertex) = 0.
A graph with more than two vertices has connectivity one iff
connected and has a cut-vertex.
5 / 39

Cut & Edge-Connectivity
Definition
Disconnecting Set (DS(G )) = {F |F ⊆ E (G ) ∧ G \ F has more tha
component}.
Definition
The edge-conectivity of (G), written as κ0
(G ), is the minimum size of a
disconnecting set S such that V \ S is disconnected.
Definition
A graph is k-edge-connected if its edge-connectivity is atleast k.
k-Edge-Connected Graph is a graph where every DS(G ) has at le
edges i.e.deletion of any (k − 1) edges can not make it disconnec
6 / 39

Edge Cut
Definition
Given S , T ⊆ V (G ), [S , T ] is a set of edges having one endpoin
the other endpoint in T .
Definition
Edge Cut = {[S, S]|S 6= φ ∧ S ⊂ V (G ) ∧ S = V (G ) \ S.Every minimal
disconnecting set is an edge cut.
Every edge cut is a disconnecting set but the converse is not tru
7 / 39

Outline
1 Basic Definitions
2 Connectivity
3 Edge-Connectivity
4 2-Connected Graphs
5 k-connected and k-edge-connected graphs
8 / 39

Connectivity of Hypercube
Theorem
κ(Qk) = k.
Proof:
For k ≥ 2, the neighbors of one vertex in Qk form a vertex cut, so
κ(Qk) ≤ k. Now we have to show that every vertex cut has size a
We use induction on k.
Basis Step:For k ≤ 1, Qk = Kk+1. This implies that
κ(Qk) = κ(Kk+1) = k.
Induction Step:For k ≥ 2, Qk is made up of two copies of Qk−1, Q and
Q0
. By induction hypothesis,

Connectivity of Hypercube
Let S be a vertex cut in Qk. If Q \ S is connected and Q0\ S is
connected, then Qk \ S is also connected unless S contains at least o
endpoint of every matched pair.This implies |S | ≥ 2k−1, but 2k−1 ≥ k for
k ≥ 2. Hence we may assume that Q \ S is disconnected.This implies by
the induction hypothesis that S has at least k − 1 vertices in Q.
If S contains no vertices in Q0
, Q0\ S is connected and allvertices of
Q \ S have neighbors in Q0\ S, so

Outline
1 Basic Definitions
2 Connectivity
3 Edge-Connectivity
4 2-Connected Graphs
5 k-connected and k-edge-connected graphs
11 / 39

Theorems
Theorem
κ0
(G ) ≤ δ(G ).
Proof.
The edges incident to a vertex v of minimum degree form an ed
Therefore, κ0
(

Theorems
Case 2:We choose x ∈ S and y ∈ S such that x and y are not adj
to each other.
T = {Set of vertices in S that are adjacent to x } ∪ {Set of vertic
S \ x that are adjacent to some vertices in S }.Every path from x to y
must pass though T, so T is a vertex cut.
Also picking the edges from x to T ∩ S and one edge from each v
T ∩ S to S yields |T | distinct edges of [S , S ].Thus,
κ0
(G ) = [S, S] ≥ |T | ≥ κ(G ).
13 / 39

Theorems
14 / 39

Theorems
Theorem
If G is a 3-regular graph, then κ(G ) = κ0
(G ).
Proof.
Let S be a minimum vertex cut, i.e., |S | = κ(G ).Since κ(G ) ≤ κ0
(G ), we
only have to construct an edge cut of size |S | = κ(G ).
Let H1 and H2 be two components of G \ S.Since S is a minimum vert
cut, and G is a 3-regular graph, each v ∈ S has a neighbor in H1 and a
neighbor in H2. The third neighbor may be in H

Theorems
16 / 39

Theorems
Theorem
If S is a set of vertices in G , then |[S , S ]| = [
P
v∈S d (v )] − 2e(G [S ]),
where G [S ] is a subgraph of G induced by S , and [S , S ] is an e
Proof.
An edge in G [S ] contributes twice to
P
v∈S d (v ).
An edge in [S , S ] contributes once to
P
v∈S d (v ).
Since it counts allcontributions to
P
v∈S d (v

Theorems
Theorem
If G is a simple graph and |[S , S ]| < δ(G ) for some non-empty p
subset S of V (G ), then |S | > δ(G ).
Proof.
|[S , S ]| < δ(G )
[S , S ]| = [
P
v∈S d (v )] − 2e(G [S ])
[P
v∈S d(v )] − 2e(G [S]) < δ(G )
|S |.δ(

Outline
1 Basic Definitions
2 Connectivity
3 Edge-Connectivity
4 2-Connected Graphs
5 k-connected and k-edge-connected graphs
19 / 39

2-Connected Graphs
Definition
Two paths from u to v are internally disjoint if they have no com
internalvertex.
Theorem
(Whitney [1932a]) A graph G having at least three vertices is 2-c
if and only if for each pair u, v ∈ V(G) there exist internally disjoi
v-paths in G.
Proof
If For every pair u, v ∈ V (G ), there exist internally disjoint u, v-
G. Deletion of one vertex cannot make u unreachable from v.Therefore, G
is 2-connected.
Only If Suppose that G is 2-connected.We prove by induction on d(u,
(distance from u to v) that G has internally disjoint u, v-paths for
pair u, v ∈ V (G ).
20 / 39

2-Connected Graphs
Basis step (d(u, v) = 1).When d(u, v) = 1, the graph G - uv is
connected, since κ(G ) ≥ 2 and κ0
(G ) ≥ κ(G ) ≥ 2.An internally disjoint
u, v-path in G - uv exists apart from the edge uv itself.
Induction step (d(u, v) > 1).Let k = d(u, v).Let w be the vertex befo
v on a shortest u, v-path; we have d(u, w) = k - 1.By the induction
hypothesis, G has internally disjoint u, w-paths P and Q.
Case 1:v ∈ V(P) ∪ V(Q). We find two internally disjoint paths in t
cycle P ∪ Q: u to v and u to v through w.
Case 2:v /∈ V(P) ∪ V(Q). Since G is 2-connected, G - w is connect
and contains a u, v-path R.
Case 2a:If R avoids P or Q, we are done.
Case 2b:R may share internalvertices with both P and Q. Let z be th
last vertex of R before v belonging to P ∪ Q. By symmetry, we m
assume that z

2-Connected Graphs
22 / 39

Expansion Lemma
Theorem
(Expansion Lemma) If G is a k-connected graph, and G0 is obtained from
G by adding a new vertex y with at least k neighbors in G, then G0 is
k-connected.
Proof.
We prove that a vertex cut S of G0 must have size at least k.
Case 1:y ∈ S. S - {y} separates G, so |S| ≥ k + 1.
Case 2:y /∈ S and N(y) ⊆ S. Since |N(y )| ≥ k implies |S| ≥ k.
Case 3:0 ≤ |N(y ) ∩ S| < k.y and N(y) - S lie in a single component
G0− S. Therefore, if S does not separate G, then G0− S is a connected
graph.Contrapositively, If G0−

Expansion Lemma
24 / 39

Characterization of 2-Connected Graphs
Theorem
For a graph G with at least three vertices, the following condition
equivalent.
A) G is connected and has no cut-vertex.
B) For allx, y ∈ V(G), there are internally disjoint x, y-paths.
C) For allx, y ∈ V(G), there is a cycle through x and y.
D) δ(G ) ≥ 1, and every pair of edges in G lies on a common cycl
Proof Whitney’s Theorem proves A ⇔ B.
For B ⇔ C, note that cycles containing x and y correspond to pair
internally disjoint x, y-paths.
For D ⇒ C, the condition δ(G ) ≥ 1 implies that vertices x and y a
isolated; we then apply the last part of D to edges incident to x aIf
there is only one such edge, then we use it and any edge inciden
third vertex.
25 / 39

2-Connected Graphs
For {A, C} ⇒ D. Since G is connected, δ(G ) ≥ 1.Now consider two
edges uv and xy.Add to G the vertices w with neighborhood {u, v}
with neighborhood {x, y}.Since G is 2-connected, the Expansion Lem
implies that the resulting graph G0 is 2-connected.
Hence condition C holds in G0
, so w and z lie on a cycle C in G0
. Since w,
z each have degree 2, C must contain the paths u, w, v and x, z,
the edges uv or xy.Replacing the paths u, w, v and x, z, y in C with
edges uv and xy yields the desired cycle through uv and xy in G
26 / 39

2-Connected Graphs
27 / 39

Outline
1 Basic Definitions
2 Connectivity
3 Edge-Connectivity
4 2-Connected Graphs
5 k-connected and k-edge-connected graphs
28 / 39

k-Connected Graphs
Definition
Given x, y ∈ V(G), a set S ⊆ V(G) - {x, y} is an x, y-separator or
if G -S has no x, y-path.
κ(x, y) be the minimum size of an x, y-cut.
λ(x, y) be the maximum size of a set of pairwise internally disjoin
y-paths.
For X, Y ⊆ V(G), an X, Y-path is a path having first vertex in X, la
vertex in Y, and no other vertex in X ∪ Y.
29 / 39

k-Connected Graphs
30 / 39

Menger Theorem
Theorem
(Menger [1927]) If x, y,are vertices of a graph G and xy /∈ E(G), then the
minimum size of an x, y-cut equals the maximum number of pai
internally disjoint x, y-paths.
Proof An x, y-cut must contain an internalvertex of every x, y-path, a
no vertex can cut two internally disjoint x, y-paths.Therefore, always κ(x
y) ≥ λ(x, y).To prove equality, we have to prove that κ(x, y) ≤ λ(
To prove κ(x, y) ≤ λ(x, y), we use induction on n(G).
Basis step:n(G) = 2.Here xy /∈ E(G) yields κ(x, y) = λ(x, y) = 0.
Induction step:n(G) > 2.Let k = κG (x, y). We construct k pairwise
internally disjoint x, y-paths.Note that since N(x) and N(y) are x, y-cu
no minimum cut properly contains N(x) or N(y).
31 / 39

Menger Theorem:Case 1
Case 1:G has a minimum x, y-cut S other than N(x) or N(y).Note that
S may contain some vertex from N(x) or N(y).
Claim 1:Let V1 be the set of vertices on x, S-paths, and let V2 be the set
of vertices on S, y-paths.S = V1 ∩ V2.
Since S is a minimum x, y-cut, every vertex of S lies on an x, y-p
hence S ⊆ V1 ∩ V2. If v ∈ (V1 ∩ V2) and v /∈ S, then following the x,
v-portion of some x, S-path and then the v, y-portion of some S,
yields an x, y-path that avoids the x, y-cut S. This is impossible,
V1 ∩ V2 ⊆ S. Therefore, S = V1 ∩ V2.
Since S contains neither N(x) nor N(y), V1 omits N(y) \ S and V2

Menger Theorem:Case 1
33 / 39

Menger Theorem:Case 1
Form H1 by adding to G[V1] a vertex y0 with edges from S.
Form H2 by adding to G[V2] a vertex x0 with edges to S.
Every x, y-path in G starts with an x, S-path (contained in H1), so every x,
y0
-cut in H1 is an x, y-cut in G. Therefore, κH1(x, y0
) = k, and similarly
κH2(x0
, y) = k.
Since V1 omits N(y) \ S and V2 omits N(x) \ S, both H1 and H2 are
smaller than G. Hence the induction hypothesis yields
λH1(x , y

Menger Theorem:Case 2
Case 2:Every minimum x, y-cut is N(x) or N(y).Again we construct the
k desired paths.
If there exists u ∈ N(x) ∩ N(y), then u appears in every x, y-cut,
κG−u(x, y ) = k − 1.Now applying the induction hypothesis to G - u
k - 1 paths to combine with the path x, u, y.
We may thus assume that N(x) and N(y) are disjoint.Let G0 be the
bipartite graph with bipartition N(x), N(y) and edge set [N(x), N(y
Every x, y-path in G uses some edge from N(x) to N(y), so the x,
G are precisely the vertex covers of G0
. Hence β(G0
) = k. By the
Konig-Egervary Theorem, G0 has a matching of size k.These k edges yiel
k pairwise internally disjoint x, y-paths of length 3.
35 / 39

Menger Theorem:Case 2
36 / 39

Line Graph
Definition
The line graph of a graph G, written L(G), is the graph whose ver
the edges of G, with ef ∈ E(L(G)) when e = uv and f = vw in G.
λ0
(x, y) is the maximum size of a set of pairwise edge-disjoint x,
κ0
(x, y) is the minimum number of edges whose deletion makes
unreachable from x. 37 / 39

Theorems
Theorem
If x and y are distinct vertices of a graph or digraph G, then the m
size of an x, y-disconnectig set of edges equals the maximum nu
pairwise edge-disjoint x, y-paths.
Proof.
Modify G to obtain G0 by adding two new vertices s, t and two new
sx and yt.This does not change κ0(x, y) or λ0(x, y), and we can think of
each path as starting from the edge sx and ending with the edgeA set
of edges disconnects y from x in G if and only if the correspondin
of L(G0
) form an sx, yt-cut.Similarly, edge-disjoint x, y-paths in G
become internally disjoint sx, yt-paths in L(G0
), and vice versa.Since x 6=
y, we have no edge from sx to ty in L(G0
). Applying Menger’s Theorem
L(G0
) yields
κ0
G (x, y) = κL(G0)(sx, yt) = λL(G0)(sx, yt) = λ0
G (x, y).
38 / 39

Theorems
39 / 39