Solution to Proof that an undirected graph has an even number of vertices of odd degree. - Sikademy
Author Image

Archangel Macsika

Proof that an undirected graph has an even number of vertices of odd degree.

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

Let G be a graph with e edges and n vertices v1,v2,v3,...,vn.

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:∑^n_{i=1}degree(v_i)=2e


Let the degrees of first r vertices be even and the remaining (n−r) vertices have odd degrees, then:

∑^n_{i=1}degree(v_i)=∑^r_{i=1}degree(v_i)+∑^n_{i=r+1}degree(v_i)


\implies ∑^n_{i=1}degree(v_i)+∑^r_{i=1}degree(v_i)


\implies ∑^n_{i=r+1}degree(v_i) is even.


But, the for i=r+1,r+2,...,n each d(v_i) is odd. So, the number of terms in

∑^n_{i=r+1}degree(v_i) must be even. So, (n-r) is even.

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-528-qpid-413