GATE CSE 1995 | Question: 24

Question

Prove that in finite graph, the number of vertices of odd degree is always even.

Comments

Simple graph

---

can we do something like:

let the degree of node be 2n+1, where n← [0,infi);

now, by handshaking theorem 2*|E| = 2n₁+1 + 2n₂+1 + 2n₃+1 …… 2nₖ+1, for k vertices;

2*|E| = 2(n₁+n₂+n₃ .. +nₖ) + k;

Now, for the above expression to be even, 2(n₁+n₂+n₃ .. +nₖ)  is already even, which implies k needs to be even as well, where k is the number of nodes;

hence, the number of nodes needs to be even.

---

Yes. And also add even degree vertices in your proof.

---

palashbehra5

Here, they are specifically asking for odd degree vertices! the total number of nodes can be even or odd right ? 

suppose a  graph has 7 nodes with a degree sequence  of   6,5,5,4,4,2,2  now this is a graphical sequence but  if the degree sequence was  6,5,5,5,4,4,2 then it is not a graphical sequence.

thus the number of odd degree vertices should be even always!

 

Answer 1

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.

Answer 2

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.

Answer 3

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.