The Gateway to Computer Science Excellence
+6 votes
Show that the number of odd-degree vertices in a finite graph is even.
in Graph Theory by Boss (30.2k points)
retagged by | 330 views

2 Answers

+7 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 (557 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.7k points)
edited by
that is not a proof..
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,549 answers
101,555 users