Handshaking Theorem-
Handshaking Theorem is also known as Handshaking Lemma or Sum of Degree Theorem.
| In Graph Theory,
Handshaking Theorem states in any given graph, Sum of degree of all the vertices is twice the number of edges contained in it. |
The following conclusions may be drawn from the Handshaking Theorem.
In any graph,
- The sum of degree of all the vertices is always even.
- The sum of degree of all the vertices with odd degree is always even.
- The number of vertices with odd degree are always even.
PRACTICE PROBLEMS BASED ON HANDSHAKING THEOREM IN GRAPH THEORY-
Problem-01:
A simple graph G has 24 edges and degree of each vertex is 4. Find the number of vertices.
Solution-
Given-
- Number of edges = 24
- Degree of each vertex = 4
Let number of vertices in the graph = n.
Using Handshaking Theorem, we have-
Sum of degree of all vertices = 2 x Number of edges
Substituting the values, we get-
n x 4 = 2 x 24
n = 2 x 6
∴ n = 12
Thus, Number of vertices in the graph = 12.
Problem-02:
A graph contains 21 edges, 3 vertices of degree 4 and all other vertices of degree 2. Find total number of vertices.
Solution-
Given-
- Number of edges = 21
- Number of degree 4 vertices = 3
- All other vertices are of degree 2
Let number of vertices in the graph = n.
Using Handshaking Theorem, we have-
Sum of degree of all vertices = 2 x Number of edges
Substituting the values, we get-
3 x 4 + (n-3) x 2 = 2 x 21
12 + 2n – 6 = 42
2n = 42 – 6
2n = 36
∴ n = 18
Thus, Total number of vertices in the graph = 18.
Problem-03:
A simple graph contains 35 edges, four vertices of degree 5, five vertices of degree 4 and four vertices of degree 3. Find the number of vertices with degree 2.
Solution-
Given-
- Number of edges = 35
- Number of degree 5 vertices = 4
- Number of degree 4 vertices = 5
- Number of degree 3 vertices = 4
Let number of degree 2 vertices in the graph = n.
Using Handshaking Theorem, we have-
Sum of degree of all vertices = 2 x Number of edges
Substituting the values, we get-
4 x 5 + 5 x 4 + 4 x 3 + n x 2 = 2 x 35
20 + 20 + 12 + 2n = 70
52 + 2n = 70
2n = 70 – 52
2n = 18
∴ n = 9
Thus, Number of degree 2 vertices in the graph = 9.
Problem-04:
A graph has 24 edges and degree of each vertex is k, then which of the following is possible number of vertices?
- 20
- 15
- 10
- 8
Solution-
Given-
- Number of edges = 24
- Degree of each vertex = k
Let number of vertices in the graph = n.
Using Handshaking Theorem, we have-
Sum of degree of all vertices = 2 x Number of edges
Substituting the values, we get-
n x k = 2 x 24
k = 48 / n
Now,
- It is obvious that the degree of any vertex must be a whole number.
- So in the above equation, only those values of ‘n’ are permissible which gives the whole value of ‘k’.
Now, let us check all the options one by one-
- For n = 20, k = 2.4 which is not allowed.
- For n = 15, k = 3.2 which is not allowed.
- For n = 10, k = 4.8 which is not allowed.
- For n = 8, k = 6 which is allowed.
Thus, Option (D) is correct.
To gain better understanding about Handshaking Theorem,
Next Article- Graph Isomorphism
Get more notes and other study material of Graph Theory.
Watch video lectures by visiting our YouTube channel LearnVidFun.
