3

I am trying to solve problem described in the title.

What I've tried

I tried to consider simple examples of graph with 0, 1 and 2 vertices and figured out that every edge has start node and end node, so number of edges can be calculated as follows:
E - number of edges in graph
Nd - degree of node $$E=\frac{\sum Nd}{2}$$ Since number of edges must be integer, $\sum Nd$ must be even. It is only even if there is even number of odd sum components.

Questions

Is this enough to prove the conjecture?
Is there other way to prove that?

Community
  • 1
M. Twarog
  • 133
  • 4
    Thats fine. The only thing you could elaborate a little more, is the last point you make, e.g. by looking at the equation $\mod 2$ and splitting of the nodes with even degree. But that's more a matter of "how super-rigoros do I want it to be?". – maxmilgram Oct 29 '19 at 06:45
  • Hi and welcome to MSE, the question is well written and follow MSE codes, but that's a very redundant question... https://math.stackexchange.com/questions/181833/proving-that-the-number-of-vertices-of-odd-degree-in-any-graph-g-is-even?rq=1 or https://math.stackexchange.com/questions/407250/the-number-of-odd-degree-vertices-is-even-in-a-finite-graph?rq=1 or https://math.stackexchange.com/questions/1760467/prove-that-graph-with-odd-number-of-odd-degree-vertices-does-not-exist?rq=1 or other I can't include because the comment is too long – Thomas Lesgourgues Oct 29 '19 at 07:13

1 Answers1

1

You are correct, and this is a standard proof for this problem.

The handshaking lemma states that the sum of all degrees is 2 times the number of edges. But, this can be broken up into those vertices that have an even degree (call them $V_{even}$) and those that have an odd degree ($V_{odd}$). That is,

$$2E = \sum_{u \in V}deg(u) = \sum_{u \in V_{even}}deg(u) + \sum_{u \in V_{odd}}deg(u)$$.

Since the number of edges $E$ is an integer, then $2E$ is an even number. Also, the sum of degrees for all vertices with even degrees $\sum_{u \in V_{even}}deg(u)$ is an even number. So we have $$evenNumber = evenNumber + \sum_{u \in V_{odd}}deg(u)$$

Since the other elements are even, necessarily $\sum_{u \in V_{odd}}deg(u)$ is an even number, too. Which means there is an even number of elements with an odd degree because otherwise the sum would be an odd number.

Heather Guarnera
  • 538