The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 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 (420k points)
edited by | 175 views

1 Answer

+2 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.
by Active (1.1k points)

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
50,362 questions
55,787 answers
90,922 users