+4 votes
287 views
Show that the number of odd-degree vertices in a finite graph is even.

retagged | 287 views

## 2 Answers

+5 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})+Σ_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$ even+odd=odd & even+even=even)

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

So, for $\sum_d(V_{odd})$  to be Even,

Number of odd-degree vertices should be even ($\because$ only when we add an even number of odd numbers we get an even number).

by Junior (519 points)
selected by
+2 votes
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.
by Veteran (62.2k points)
edited by
+3
that is not a proof..

+2 votes
1 answer
1
+27 votes
3 answers
2
+15 votes
2 answers
3
0 votes
2 answers
4
+1 vote
1 answer
5
+9 votes
2 answers
7