TIFR CSE 2012 | Part B | Question: 2

Question

In a graph, the degree of a vertex is the number of edges incident (connected) on it. Which of the following is true for every graph $G$?

• A. There are even number of vertices of even degree.
• B. There are odd number of vertices of even degree.
• C. There are even number of vertices of odd degree.
• D. There are odd number of vertices of odd degree.
• E. All the vertices are of even degree.

Answer 1

As we know that sum of degree of vertex $= 2\times edges.$
let there is $u$ vertex with odd degrees and $v$ vertex with even degrees.

Then $\sum\left(u\right) + \sum\left(v\right) = 2e.$
now $2e = \text{even}.$
$\sum\left(v\right) =$ sum of even number will be even.
$\sum\left(u\right) =$ if you consider odd number of vertices of odd degree then sum will be odd and this will violate $2e$
so there will be always the even number of vertices with odd degree

Hence, Ans is (c)There are the even number of vertices of odd degree.

Comments

Thanks .. got it ..

---

What would had been the result if graph given is directed??

---

A tree is a special type of graph. Option C won’t hold true for it.

Answer 2

So option C

Answer 3

Always there are even number of vertices of odd degree in the graph. Hence option C is correct