a Draw a graph with five vertices having degrees 2 2 3 4 4

a. Draw a graph with five vertices having degrees 2, 2, 3, 4, 4 ; or explain why such graph does not exist.

b. *Bonus question: A graph is called simple if it has no loops or multi-edges. Does a simple graph exist with all vertices having different degrees? Hint: Google then use “pigeonhole principle”.

Solution

a.

Sum of degrees of all vertices of a graph =2*(Number of edges in the graph)

So sum of degrees is even

But in the given degrees all are even except one with degree 3 so the sum of degrees is odd.

Hence such a graph does not exist

b.

Let the graph have n vertices

SO any vertex have have atmost n-1 degree and we have n vertices

For all the degrees to be different the degrees must be

0,1,2,...,n-1

But a vertex of degree n-1 means a vertex connected to all the vertices

And a vertex of degree 0 means a vertex connected to none of the vertices

Hence, such a graph is not possible.