I need to prove that it is impossible to have a graph in which there are an odd number of odd degree vertices. What is the easiest way to formally prove this? I feel that I can prove it just by explaining that the sum of the degree of a graph must be equal to twice the number of edges, which implies that there must be a total even degree, but this isn't very formal.

I'm thinking proof by contradiction, but I'm not too sure where to begin.

  • $\begingroup$ This is the handshaking lemma, right? $\endgroup$ – GAVD Apr 27 '16 at 1:59
  • $\begingroup$ Right. Which I understand and can demonstrate that its true, but as far as writing a formal proof, I'm lost. $\endgroup$ – dibdub Apr 27 '16 at 2:00
  • $\begingroup$ What exactly do you not find formal about your line of reasoning? Oddness and evenness are formal properties of integers. They obey formal laws of addition. Too many students confuse "rigor" with "using lots of symbols at the expense of readability" :). $\endgroup$ – Erick Wong Apr 27 '16 at 2:35
  • $\begingroup$ Well the problem states specifically to "use one of the proof methods we used before". We've learned induction, contradiction, pigeonhole principle, and a few others. I would assume that our professor wants us to use one of those specifically, and I don't really feel that my line of reasoning falls into one of those. $\endgroup$ – dibdub Apr 27 '16 at 2:39

You need to prove a little lemma:

(1) Sum of evens is even.

(2) Sum of odd number of odds is odd.

Prove (1) by factoring out a $2$, and prove (2) by induction on the number of terms. Then we can prove what you want.

$E(G)=\{v\in V(G):d(v)\text{ is even}\}$

$O(G)=\{v\in V(G):d(v)\text{ is odd}\}$

$\sum_{v\in V(G)} d(v) =\sum _{v\in E(G)}d(v)+ \sum _{v\in O(G)}d(v)$ is even.

$\sum _{v\in E(G)}d(v)$ is also even, so $\sum _{v\in O(G)}d(v)=\sum_{v\in V(G)} d(v)-\sum _{v\in E(G)}d(v)$ is even.

Therefore $\mid O(G)\mid$ is even.


The same proof of Forever Mozart explained differently is as follows:

Consider that such a graph exists and consider its incidence matrix. The sum of the numbers in column must be $2$ for each edge is incident on exactly $2$ vertices. It follows that the sum of all the numbers in the matrix would be an even number.

Now the row sum for odd degree vertices would be odd because each row sums to the degree of the corresponding vertex. Since there are an odd number of odd degree vertices so there will be an odd number of odd row sums following which the sum of all the row sums would be odd. In other words the sum of all the numbers in the matrix would be an odd number. This is a contradiction.


For a proof by contradiction, suppose you have a graph with odd number of odd degree vertices, say $\{v_1,\dots,v_k\}$. Then $d(v_1)+\dots+d(v_k)$ is odd.

The remaining vertices $\{v_{k+1},\dots,v_n\}$ have even degrees, so $d(v_{k+1})+\dots+d(v_n)$ is even.

Then $\sum_{v\in V}d(v)=[d(v_1)+\dots+d(v_k)]+[d(v_{k+1})+\dots+d(v_n)]$ is odd, since an odd number plus an even number is odd.

However this contradicts the Handshaking Lemma $\sum_{v\in V}d(v)=2|E|$ which is even!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.