The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+4 votes
Show that the number of odd-degree vertices in a finite graph is even.
in Graph Theory by Boss (29.5k points)
retagged by | 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
that is not a proof..

Related questions

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
49,845 questions
54,785 answers
80,449 users