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

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).

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.

### 1 comment

that is not a proof..

$\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.

1
3,101 views