Can a graph have 5 vertices of degrees 1, 2, 3, 4 and 5? Either draw such a graph or explain why it can not exists.

Knowledge:

• For the existence of a graph, sum of degrees of the graph should be an even number.
• An undirected graph has an even number of vertices of odd edges.
• Handshaking Lemma: In every finite undirected graph, the number of vertices that touch an odd number of edges is even. i.e. In an undirected graph, the total number of edges in a graph is equal to half the sum of the degrees.

Answer:

Sum of the degrees of vertices = 1+2+3+4+5 = 15 ; odd

Since sum of the degrees of the graph is a odd number, graph does not exists.

If question be; Can a graph have 5 vertices of degrees 1, 2, 3 and 4 ? Either draw such a graph or explain why it can not exists.

• Sum of the degrees of vertices = 1+2+3+4 = 10 ; even
• Since sum of the degrees of the graph is an even number, graph exists.

Graph

Thank you for reading.

By Thaveesha Handapangoda. For videos click here