Register

GO CLASSES DPP | Discrete Mathematics | Graph theory | TIFR

• retagged by
488 views
2 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. At least one of $d$ and $n$ is even
  3. Both $d$ and $n$ are odd
  4. At least one of $d$ and $n$ is odd
     

4 Answers

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

Now, sum of degrees is $n d$, as there are $n$ vertices of degree $d$ each.
As $n d$ is even, either one of them should be definitely even.
• reshown by
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO CLASSES DPP | Dis...Next → · GO CLASSES DPP | Dis...
← Previous in category · GO CLASSES DPP | Dis...Next in category → · GO CLASSES DPP | Dis...
Position:
Show:

Related questions

2 2 votes
3 3 answers
477
477 views
GO Classes asked Jul 23, 2025
477 views
GO CLASSES DPP | Discrete Mathematics | Graph theory | TIFR
Let $G=(V, E)$ be an undirected simple graph. A subset $M \subseteq E$ is a matching in $G$ if distinct edges in $M$ do not share a vertex. A matching is maximal if no st...
3 3 votes
3 3 answers
623
623 views
GO Classes asked Jul 23, 2025
623 views
GO CLASSES DPP | Discrete Mathematics | Graph theory | UGC NET
The minimum number of edges in a connected graph with ${ }^{\prime} n^{\prime}$ vertices is equal to$n(n-1)$ $\frac{n(n-1)}{2}$ $n^2$ $n-1$
2 2 votes
2 2 answers
490
490 views
GO Classes asked Jul 23, 2025
490 views
GO CLASSES DPP | Discrete Mathematics | Graph theory | UGC NET
The number of edges in a complete graph of $n$ vertices is$n$ $n(n-1) / 2$ $n(n+1) / 2$ $\left(n^{\wedge} 2\right) / 2$
1 1 vote
2 2 answers
386
386 views
GO Classes asked Jul 23, 2025
386 views
GO CLASSES DPP | Discrete Mathematics | Graph theory | UGC NET
An undirected graph possesses an eulerian circuit if and only if it is connected and its vertices areAll of even degreeAll of odd degreeOf any degreeEven in number