Question

Draw a connected, simple graph with 6 vertices and 12 edges. Verify the Handshaking Lemma for your graph.

Answer 1

Handshaking lemma states that: The sum of degrees of all the vertices in a graph G defined as G(V,E) is equal to twice the number of edges in that graph.

i.e,

Now, let’s draw a simple connected undirected graph with 6 vertices and 12 edges to verify the lemma

Here, in the graph shown above, we have the number of edges E = 12 and Vertices V = 6

Now, let’s add the degrees of all the vertices,

We can observe that the degree of each red coloured vertex is 4 and that of yellow coloured vertex is 5 and blue coloured vertex is 3 so for 6(4red + 1yellow + 1blue) vertices we have,

…(1)

^{Also, We have twice of the number of edges E = = 2 * 12 = 24}          …(2)

So, from (1) and (2), it can be seen that Handshaking Lemma holds for the given example hence verified.