recategorized by
5,678 views
19 votes
19 votes
Prove that in finite graph, the number of vertices of odd degree is always even.
recategorized by

3 Answers

Best answer
28 votes
28 votes

In any finite graph,

  • Sum of the degree of all the vertices $= 2\;\times$ number of edges
  • Sum of the degree of all the vertices with even degree $+$ sum of the degree of all the vertices with odd degree $= 2\;\times$ number of edges
  • Even number  $+$ sum of the degree of all the vertices with odd degree $=$ an even number.

It is possible only if the number of odd degree vertices is even.

edited by
1 votes
1 votes
Let G be a graph with $'e'$ edges and $'n'$ vertices $v_1,v_2,v_3,...,v_n$. Since each edge is incident on two vertices, it contributes $2$to the sum of degree of vertices in graph $G$. Thus the sum of degrees of all vertices in $G$ is twice the number of edges in $G$. Hence, $$\sum_{i=1}^n\text{degree}(v_i)= 2e.$$ Let the degrees of first $r$ vertices be even and the remaining $(n-r)$ vertices have odd degrees,then clearly,$\sum_{i=1}^{r}\text{degree}(v_i)= even $.Since,$$\sum_{i=1}^n\text{degree}(v_i)= \sum_{i=1}^r\text{degree}(v_i)+\sum_{i=r+1}^n\text{degree}(v_i)$$ $\implies$ $\sum_{i=1}^n\text{degree}(v_i)- \sum_{i=1}^r\text{degree}(v_i)=\sum_{i=r+1}^n\text{degree}(v_i)$

$\implies$ $\sum_{i=r+1}^n\text{degree}(v_i)$ is even.($WHY?$)

But, the for $i=r+1,r+2,...,n$ each $d(v_i)$ is odd. So, the number of terms in $\sum_{i=r+1}^n\text{degree}(v_i)$ must be even.

In lucid words,$(n-r)$ is even.

Hence the result.
1 votes
1 votes

d(v1) → means degree of vertex V1

Let us suppose there is some graph with n number of vertices.

d(V1) + d(V2) + d(V3) + d(V4) ………. d(Vn) = 2 * Total number of edges

Why this formula holds true, because every edge is going to contribute 2 to the total sum of degrees, hence R.H.S. is strictly an EVEN number.

Rewriting the equation …

d(V1) + d(V2) + d(V3) + d(V4) ………. d(Vn) = EVEN NUMBER

you can observe that the L.H.S. can be divided into two sets, S1 and S2

S1 = Vertices with even degree

S2 = Vertices with ODD degree

We care about S2 so let’s try to take off S1 from the equation.

S1 + S2 = EVEN NUMBER

S1 will be strictly an even number because inside S1 every vertex is of even degree.

EVEN + S2 = EVEN NUMBER 

→  S2  = EVEN NUMBER – EVEN

→ S2 = EVEN NUMBER

now coming to S2, we know every vertex inside S2 had odd degree

ODD + ODD = EVEN

ODD + ODD + ODD = ODD

We can see that for the final sum to be even we must have even number of vertices with odd degree.

Related questions

15 votes
15 votes
3 answers
1
makhdoom ghaya asked Nov 14, 2016
1,794 views
Show that the number of odd-degree vertices in a finite graph is even.
48 votes
48 votes
3 answers
2
Arjun asked Nov 15, 2015
4,294 views
Show that all vertices in an undirected finite graph cannot have distinct degrees, if the graph has at least two vertices.
2 votes
2 votes
0 answers
3
11 votes
11 votes
3 answers
4
Kathleen asked Oct 8, 2014
1,490 views
Prove using mathematical induction for $n \geq 5, 2^n n^2$