GATE CSE 1987 | Question: 9c

Question

Show that the number of odd-degree vertices in a finite graph is even.

Answer 1

For proving this we should know that 

$\sum_d(V) =2e \quad \to(1)$

Because one edge consist of two vertices and hence contributes two degrees.

For any Graph $G$

$\sum_d(V)=\sum_d(V_{odd})+\sum_d(V_{even}) \quad \to(2)$

From $(1)$ we can say that $\sum_d(V)$ should be even.

$\sum_d(V_{even})$ will be always even ($\because$ sum of even numbers is always even)

So, for $(2)$ to be true  $\sum_d(V_{odd})$ should be even  ($\because \text{even}+\text{odd}=\text{odd}$ & $\text{even}+\text{even}=\text{even})$

In $\sum_d(V_{odd}),$ every degree is odd.

So, for $\sum_d(V_{odd})$  to be Even, the number of odd-degree vertices should be even ($\because$ only when we add an even number of odd numbers, we get an even number).

Answer 2

Question. Will be number of odd degree vertex in finite graph is even.

Take any random graph I.e. $K_3$ have $0$ odd degree  vertex and $K_4$ has even $(4)$ odddegree vertex.

Simple line has $2$(even) vertex with odd degree.

Comments

that is not a proof..

Answer 3

$\underbrace{1+3}=4$

even # of odd numbers.

$\underbrace{1+3+5}=9$

odd # of odd numbers

---

Handshaking Lemma: $\sum$ (degree of V) $=2$ (number of edges)

$\sum$ (odd degree vertices) $+\sum$ (even degree vertices) $=2m$ (even)

$\underbrace{d_1+d_2+d_3+d_4+….d_n}=2m$ (even)

                Even number

1. All are even numbers.
2. There are even # of odd numbers.

$\sum$ (even degree vertices) always even.

$\sum$ (odd degree vertices) in order to make this also even there should be even # of odd degree vertices in the graph.