Dark Mode

1,218 views

20 votes

Best answer

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

0 votes

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

- All are even numbers.
- 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.