5 votes 5 votes 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? $d$ divides $n$ Both $d$ and $n$ are even Both $d$ and $n$ are odd At least one of $d$ and $n$ is odd At least one of $d$ and $n$ is even Graph Theory tifr2019 graph-theory degree-of-graph + – Arjun asked Dec 18, 2018 retagged Nov 21, 2022 by Lakshman Bhaiya Arjun 1.6k views answer comment Share Follow See 1 comment See all 1 1 comment reply chirudeepnamini commented Dec 11, 2019 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.
Best answer 14 votes 14 votes 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. Gokulnath answered Dec 18, 2018 selected Jan 25, 2020 by Shaik Masthan Gokulnath comment Share Follow See all 0 reply Please log in or register to add a comment.