TIFR CSE 2019 | Part B | Question: 3

Question

A graph is $d$ – regular if every vertex has degree $d$. For a $d$ – regular graph on $n$ vertices, which of the following must be TRUE?

• A. $d$ divides $n$
• B. Both $d$ and $n$ are even
• C. Both $d$ and $n$ are odd
• D. At least one of $d$ and $n$ is odd
• E. At least one of $d$ and $n$ is even

Comments

Counter example for

A,B,C-- cycle of 3 vertices. n=3,d=2

D-- cycle of 4 vertices. n=4,d=2.

Now assume that option e is false.

I.e.,both n,d are odd. I.e there are odd number of vertices with odd degree... Which is violating the property of graph that "there are even number of vertices of odd degree in a graph"

Hence our assumption is false and option E is true.

Answer 1

We know that the sum of degrees is twice the number of edges.

Now, sum of degrees is $nd$, as there are $n$ vertices of degree $d$ each.

As $nd$ is even, either one of them should be definitely even.

Answer 2

n vertices

d degrees

e edges

Then,

nd = 2e

n or d must be Even, Option E is the Correct