1

This elementary result is normally stated as a corollary to the Handshaking Lemma, which says nothing about it other than that it's true. I wonder if there is more depth to this fact, in particular if there are any essentially different proofs and/or arguments visualizing why this should be true... Thanks!

Martin Sleziak
  • 53,687
Damian Reding
  • 8,773
  • Just count vertex-edge incidences in two ways ... – Hagen von Eitzen Apr 11 '16 at 14:49
  • I think this question seems like it is either a duplicate of http://math.stackexchange.com/questions/181833/proving-that-the-number-of-vertices-of-odd-degree-in-any-graph-g-is-even?rq=1 or too broad. In either case it is too vague... – Ove Ahlman Apr 11 '16 at 14:50
  • According to Wikipedia's nomenclature at least, the fact that a finite graph has an even number of odd-degree vertices is the Handshaking Lemma itself, not merely a corollary thereof ... – hmakholm left over Monica Apr 11 '16 at 14:51
  • 1
    I think neither, as the OP is asking for intuition and already knows the proof. – Stella Biderman Apr 11 '16 at 14:52
  • But if you really understand the handshaking lemma, then it's immediately intuitive why this corollary is true... – Josh Feb 25 '17 at 13:04

3 Answers3

4

First way

Every edge has two ends. Therefore the total number of edge ends is even: It is two times the number of edges.

On the other hand, the degree of a vertex is the number of edges that end at that vertex. And since all edges have a vertex at both ends, the sum of all vertex degrees is: (the total number of edges * 2), and thus even.

However the sum of all vertex degrees is the sum of all even vertex degrees plus the sum of all odd vertex degrees. The first one is obviously even, therefore the second one also has to be even. But a sum of odd numbers is only even if there is an even number of them.

Second way

Imagine you are drawing the graph. First, you draw all vertices. Since there are not yet any edges, every vertex, as of now, has degree $0$, which clearly is even. Therefore there are zero nodes of odd degree, which, again, is an even number.

Then you add the edges, one at a time. For each edge, one of the following can happen:

  • Before adding the edge, the two vertices you are going to connect both have even degree. Since each of them gets another edge, afterwards both are of odd degree. Thus the number of vertices of odd degree has increased by $2$. In particular, if it was even before, it is even afterwards.

  • Before adding the edge, the two vertices you are going to connect both have odd degree. Again because you increase the degree of both by one, they now both have even degree. Thus the number of vertices of odd degree has been reduced by $2$; in particular, if it was even before, it is even afterwards.

  • Before adding the edge, one of the vertices you are going to connect was of even degree, the other one of odd degree. Connecting them makes the even degree vertex into an odd degree vertex, and the odd degree vertex into an even degree vertex. So the number of odd degree vertices hasn't changed at all; in particular not from an even to an odd number.

So in summary, you start with a graph with an even number of odd-degree nodes (namely zero), and anything you do to change it won't change the parity of the number of odd-degree nodes, therefore you also end up with a graph that has an even number of odd-degree nodes.

Totem
  • 115
celtschk
  • 43,384
1

The handshaking lemma states that for every graph $G=(V,E)$: $$ \sum_{v\in V}\deg(v)=2m, $$ so the sum $\sum_{v\in V}\deg(v)$ has to be even. This sum can be decomposed in two sums: $$ \sum_{v\in V}\deg(v)=\sum_{v\in V|\deg(v)=2k}\deg(v)+\sum_{v\in V|\deg(v)=2k+1}\deg(v), $$ The first is clearly even, so the second one also has to be even. But if $deg(v)=2k+1$, than the number of such vertices has to be even (as an odd number of odd terms cannot be even).

Kuifje
  • 9,584
1

Assume you have a simple finite connected graph $G$ with number of vertices $V$, number of edges $E$, and with degrees $d_1,d_2, \dots,d_V$ for corresponding vertices $v_1, v_2, \dots, v_V$. Since G is simple and finite, we know that $\sum_{i=1}^{V}d_i=2E$, meaning that the sum of degrees must be an even number. If we add up even degrees, we will always get an even number. If we add up odd degrees we will only get an even number if we add up an even number of odd degrees. Therefore there must be an even number of odd degree vertices.

J. Bush
  • 1,049