Department of Mathematics Elementary Graph Theory Lecture 9
Vertex connectivity
The vertex connectivity h0 (G ) of a graph G is the minimum number of
vertices whose removal disconnects the graph G or makes it isomorphic to
the trivial graph K1 .
Ex:
1. h0 (G ) 0 iff G is disconnected. h0 ( Forest graph) 1
2. h0 (G ) 1 iff G has a cut-vertex or G K 2 h0 ( Pn ) 1
3. h0 (G ) 2 . h0 (Cn ) 2
4. h0 ( K n ) n 1 , h0 ( K 4 ) 3
5. h0 ( K m, n ) min{m, n} , , h0 ( K 4, 2 ) min{4, 2} 2
6. h0 ( petersen graph) 3
Note: h0 (G ) (G ) .
Edge connectivity
The edge connectivity h1 (G ) of a graph G is the minimum number of
edges whose removal disconnects the graph G .
Ex:
1. h1 (G ) 0 iff G is disconnected. h1 ( Forest graph) 1
2. h0 (G ) 1 iff G has a cut-edge h1 ( Pn ) 1
3. h1 (G ) 2 . h1 (Cn ) 2
4. h0 ( K n ) n 1 , h1 ( K 4 ) 3
5. h1 ( K m, n ) min{m, n} , , h1 ( K 4, 2 ) min{4, 2} 2
6. h1 ( petersen graph) 3
Dr. Didar A. Ali 1
, Department of Mathematics Elementary Graph Theory Lecture 9
Note: h1 (G ) (G ) .
Theorem: For any simple graph G, h0 (G ) h1 (G ) (G ) .
Theorem: For all integers a, b, and c, such that 0 a b c , there exist a graph G
with, h0 (G ) a , h1 (G ) b and (G ) c .
Ex: Construct a graph G in which h0 (G ) 2 , h1 (G ) 4 and (G ) 6 .
A graph G
v1 has the minimum degree which is 6, thus (G ) 6
Removing the two vertices v1 and v1 disconnected the graph G it means h0 (G ) 2 .
Removing the foure edges e1 , e2 , e3 and e4 disconnected the graph G it means
h1 (G ) 4 .
Theorem: Among all graphs of order p and size q, the maximum vertex
2q
connectivity h0 (G ) 0 , if q p 1 and h0 (G ) , where q p 1 .
p
Dr. Didar A. Ali 2
Vertex connectivity
The vertex connectivity h0 (G ) of a graph G is the minimum number of
vertices whose removal disconnects the graph G or makes it isomorphic to
the trivial graph K1 .
Ex:
1. h0 (G ) 0 iff G is disconnected. h0 ( Forest graph) 1
2. h0 (G ) 1 iff G has a cut-vertex or G K 2 h0 ( Pn ) 1
3. h0 (G ) 2 . h0 (Cn ) 2
4. h0 ( K n ) n 1 , h0 ( K 4 ) 3
5. h0 ( K m, n ) min{m, n} , , h0 ( K 4, 2 ) min{4, 2} 2
6. h0 ( petersen graph) 3
Note: h0 (G ) (G ) .
Edge connectivity
The edge connectivity h1 (G ) of a graph G is the minimum number of
edges whose removal disconnects the graph G .
Ex:
1. h1 (G ) 0 iff G is disconnected. h1 ( Forest graph) 1
2. h0 (G ) 1 iff G has a cut-edge h1 ( Pn ) 1
3. h1 (G ) 2 . h1 (Cn ) 2
4. h0 ( K n ) n 1 , h1 ( K 4 ) 3
5. h1 ( K m, n ) min{m, n} , , h1 ( K 4, 2 ) min{4, 2} 2
6. h1 ( petersen graph) 3
Dr. Didar A. Ali 1
, Department of Mathematics Elementary Graph Theory Lecture 9
Note: h1 (G ) (G ) .
Theorem: For any simple graph G, h0 (G ) h1 (G ) (G ) .
Theorem: For all integers a, b, and c, such that 0 a b c , there exist a graph G
with, h0 (G ) a , h1 (G ) b and (G ) c .
Ex: Construct a graph G in which h0 (G ) 2 , h1 (G ) 4 and (G ) 6 .
A graph G
v1 has the minimum degree which is 6, thus (G ) 6
Removing the two vertices v1 and v1 disconnected the graph G it means h0 (G ) 2 .
Removing the foure edges e1 , e2 , e3 and e4 disconnected the graph G it means
h1 (G ) 4 .
Theorem: Among all graphs of order p and size q, the maximum vertex
2q
connectivity h0 (G ) 0 , if q p 1 and h0 (G ) , where q p 1 .
p
Dr. Didar A. Ali 2
