The Gateway to Computer Science Excellence
+2 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?

  1. $d$ divides $n$
  2. Both $d$ and $n$ are even
  3. Both $d$ and $n$ are odd
  4. At least one of $d$ and $n$ is odd
  5. At least one of $d$ and $n$ is even
in Graph Theory by Veteran
edited by | 324 views
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.

1 Answer

+8 votes
Best answer
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.
by Active
selected by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,218 questions
59,891 answers
118,128 users