retagged by
1,599 views
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?

  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
retagged by

1 Answer

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.
selected by
Answer:

Related questions