Summary Graph theory

SCHOOL OF SCIENCE AND HUMANITIES
DEPARTMENT OF MATHEMATICS




UNIT – I – Advanced Graph Theory – SMT5207




1

, I. Connectivity

Contents - Connectivity and edge-connectivity – 2-connected graphs – Menger’s theorem.


Connectivity
A graph is said the connectivity of a graph. A graph with multiple disconnected
vertices and to be connected if there is a path between every pair of vertex. From
every vertex to any other vertex, there should be some path to traverse. That is called
edges is said to be disconnected.
Example 1
In the following graph, it is possible to travel from one vertex to any other vertex.
For example, one can traverse from vertex ‘a’ to vertex ‘e’ using the path ‘a-b-e’.




Example 2
In the following example, traversing from vertex ‘a’ to vertex ‘f’ is not possible
because there is no path between them directly or indirectly. Hence it is a
disconnected graph.




Cut Vertex
Let ‘G’ be a connected graph. A vertex V ∈ G is called a cut vertex of ‘G’, if ‘G-V’
(Delete ‘V’ from ‘G’) results in a disconnected graph. Removing a cut vertex from
a graph breaks it in to two or more graphs.
Note − Removing a cut vertex may render a graph disconnected. A
connected graph ‘G’ may have at most (n–2) cut vertices.
Example
In the following graph, vertices ‘e’ and ‘c’ are the cut vertices.




2

,By removing ‘e’ or ‘c’, the graph will become a disconnected graph.




Cut Set of a Graph
Let ‘G’= (V, E) be a connected graph. A subset E’ of E is called a cut set of G if
deletion of all the edges of E’ from G makes G disconnect.
If deleting a certain number of edges from a graph makes it disconnected, then those
deleted edges are called the cut set of the graph.

Example
Take a look at the following graph. Its cut set is E1 = {e1, e3, e5, e8}.




After removing the cut set E1 from the graph, it would appear as follows −




Similarly, there are other cut sets that can disconnect the graph −

E3 = {e9} – Smallest cut set of the graph.
E4 = {e3, e4, e5}
Edge Connectivity
Let ‘G’ be a connected graph. The minimum number of edges whose removal makes
‘G’ disconnected is called edge connectivity of G.

Notation − λ(G)
In other words, the number of edges in a smallest cut set of G is called the edge
connectivity of G.

3

, If ‘G’ has a cut edge, then λ(G) is 1. (edge connectivity of G.)

Example
Take a look at the following graph. By removing two minimum edges, the connected
graph becomes disconnected. Hence, its edge connectivity (λ(G)) is 2.




Here are the four ways to disconnect the graph by removing two edges −




Vertex Connectivity
Let ‘G’ be a connected graph. The minimum number of vertices whose removal
makes ‘G’ either disconnected or reduces ‘G’ in to a trivial graph is called its vertex
connectivity.

Notation − K(G)

Example
In the above graph, removing the vertices ‘e’ and ‘i’ makes the graph disconnected.




If G has a cut vertex, then K(G) = 1.

Notation − For any connected graph G,
Vertex connectivity (K(G)), edge connectivity (λ(G)), minimum number of degrees
of G(δ(G)).

Theorem (Whitney) For any graph G, κ(G) ≤ λ (G) ≤ δ (G).
Proof: We first prove λ(G) ≤ δ(G).
If G has no edges, then λ = 0 and δ = 0. If G has edges, then we get a disconnected
graph, when all edges incident with a vertex of minimum degree are removed. Thus,
in either case, λ (G) ≤ δ (G).

We now prove κ(G) ≤ λ (G). For this, we consider the various cases. If G

4