vertex connectivity Edge connectivity Matchings and Coverings Coverings

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