A Calculational Proof of the Handshaking Lemma

UPDATE (2011/09/20): This post was superseded by An improved proof of the handshaking lemma.

In graph theory, the degree of a vertex $A$, $\fapp{d}{A}$, is the number of edges incident with the vertex $A$, counting loops twice. So, considering Graph 0 below, we have $\fapp{d}{A}=3$, $\fapp{d}{B}=3$, $\fapp{d}{C}=1$, $\fapp{d}{D}=3$, and $\fapp{d}{E}=2$.

Example of an undirected graph with five nodes

Graph 0: Example of an undirected graph with five nodes

A well-known property is that every undirected graph contains an even number of vertices with odd degree. The result first appeared in Euler’s 1736 paper on the Seven Bridges of Königsberg and is also known as the handshaking lemma (that’s because another way of formulating the property is that the number of people that have shaken hands an odd number of times is even).

As we can easily verify, Graph 0 satisfies this property. There are four vertices with odd degree ($A$,$B$, $C$, and $D$), and 4, of course, is an even number.

Although the proof of this property is simple, I have never seen it proved in a calculational and goal-oriented way. My aim with this post is to show you a development of a goal-oriented proof.

Before we start, let me explain the notations that I use. I assume the existence of two predicates, $even$ and $odd$, that test the parity of numbers. For example, $\fapp{even}{8}$ and $\fapp{odd}{3}$ are both true, and $\fapp{even}{5}$ and $\fapp{odd}{6}$ are both false. Also, I use the so-called Eindhoven notation for quantifiers; for example, to express the sum of all natural even numbers less than 50 I write $\quantifier{\Sigma}{n}{0{\leq}n{<}50~\wedge~\fapp{even}{n}}{n}$, and instead of writing $\fapp{even}{0}{\equiv}\fapp{even}{1}{\equiv}{\cdots}{\equiv}\fapp{even}{50}$, I write $\quantifier{\equiv}{n}{0{\leq}n{\leq}50}{\fapp{even}{n}}$.

Now, the first step in any goal-oriented solution is to express the goal. In other words, what do we want to prove or calculate? Using the notation just described and assuming that $V$ is the set of all vertices, our goal is to determine the value of the following expression:

\[
\fapp{even}
{
\quantifier{\Sigma}{a}
{a{\in}V{\wedge}\fapp{odd}{(\fapp{d}{a})}}
{1}
}~~~.
\]
Note that we are adding 1 (counting) for each node $a$ in $V$ with an odd degree. We then apply the predicate $even$ to the result. If the result is true, there is an even number of vertices with odd degree; otherwise, there is an odd number. Our goal is thus to determine its value. (We know that it must evaluate to true, because the property is well-known. However, in general, when doing mathematics, we don't know what is the final value; that is why goal-oriented and calculational proofs are important.)

We know that the predicate $even$ distributes over addition, so we calculate:

\[
\beginproof
\pexp{\fapp{even}{\quantifier{\Sigma}{a}{a{\in}V\,{\wedge}\,\fapp{odd}{(\fapp{d}{a})}}{1}}}
\hint{=}{$even$ distributes over addition}
\pexp{\quantifier{\equiv}{a}{a{\in}V\,{\wedge}\,\fapp{odd}{(\fapp{d}{a})}}{\fapp{even}{1}}}
\hintf{=}{the most reasonable thing to do is to simplify the}
\hintm{range; this step prepares that simplification, because}
\hintm{$\quantifier{\equiv}{a}{a{\in}V\,{\wedge}\,\fapp{even}{(\fapp{d}{a})}}{true}$ is true and $\equiv$ is reflexive.}
\hintl{Also, $\fapp{even}{1}{\equiv}false$.}
\pexp{\quantifier{\equiv}{a}{a{\in}V\,{\wedge}\,\fapp{odd}{(\fapp{d}{a})}}{false} \equiv \quantifier{\equiv}{a}{a{\in}V\,{\wedge}\,\fapp{even}{(\fapp{d}{a})}}{true}}
\hint{=}{we make the terms equal, using the information in the range}
\pexp{\quantifier{\equiv}{a}{a{\in}V\,{\wedge}\,\fapp{odd}{(\fapp{d}{a})}}{\fapp{even}{(\fapp{d}{a})}} \equiv \quantifier{\equiv}{a}{a{\in}V\,{\wedge}\,\fapp{even}{(\fapp{d}{a})}}{\fapp{even}{(\fapp{d}{a})}}}
\hint{=}{range splitting}
\pexp{\quantifier{\equiv}{a}{a{\in}V}{\fapp{even}{(\fapp{d}{a})}}}
\hint{=}{$even$ distributes over addition}
\pexp{\fapp{even}{\quantifier{\Sigma}{a}{a{\in}V}{\fapp{d}{a})}}~~.}
\endproof
\]

This calculation shows that the parity of the number of vertices with odd degree is the same as the parity of the sum of all the degrees. But because each edge has two ends, the sum of all the degrees is simply twice the total number of edges. We thus have:

\[
\beginproof
\pexp{\quantifier{\equiv}{a}{a{\in}V\,{\wedge}\,\fapp{odd}{(\fapp{d}{a})}}{\fapp{even}{1}}}
\hint{=}{calculation above}
\pexp{\fapp{even}{\quantifier{\Sigma}{a}{a{\in}V}{\fapp{d}{a})}}}
\hintf{=}{the sum of all the degrees is twice the}
\hintl{number of edges, i.e., an even number}
\pexp{true~~.}
\endproof
\]

And so we can conclude that every undirected graph contains an even number of vertices with odd degree.

What is wrong with conventional solutions?

Conventional solutions for this problem are usually very similar to the following one, taken from the book “Ingenuity in Mathematics” (p. 8), by Ross Honsberger:

The proof in general is simple. We denote by T the total of all the local degrees:

(1) T = d(A) + d(B) + d(C) + … + d(K) .

In evaluating T we count the number of edges running into A, the number into B, etc., and add. Because each edge has two ends, T is simply twice the number of edges; hence T is even.

Now the values d(P) on the right-hand side of (1) which are even add up to a sub-total which is also even. The remaining values d(P) each of which is odd, must also add up to an even sub-total (since T is even). This shows that there is an even number of odd d(P)’s (it takes an even number of odd numbers to give an even sum). Thus there must be an even number of vertices with odd local degree.

There is nothing seriously wrong with this solution. It clearly shows why the property holds. However, it is, in my view, oriented to verification: it starts by introducing the total sum of all the local degrees, observing that its value is even; then it analyses that sum to conclude the property. My question is: how can we teach students to come with the total sum of all the local degrees? In general, how can we teach students to come with seemingly unrelated concepts that will be crucial in the development of their arguments? I don’t think we can.

On the other hand, if we look at the goal-oriented proof, we see that the goal is simple to express. Furthermore, with some training, most students would write it correctly and would be able to calculate that the parity of the number of vertices with odd degree is the same as the parity of the sum of all the degrees. And then (and only then) the introduction of the total sum of all the degrees would make sense. In a way, goal-oriented calculations are like that famous masked magician that reveals magic’s biggest secrets, for they reveal how the rabbit got into the hat.

Related Posts:



4 thoughts on “A Calculational Proof of the Handshaking Lemma

  1. Hi João,

    I’m a first year undergraduate student of mathematics and computer science. We have just started with graph theory and have been introduced to the handshaking lemma and its corollaries the very first hour. The proof which was presented was pretty much the same as the one you quoted and sadly, your concerns about the “students using seemingly unrelated concepts” are utterly true.

    On the other hand, the proof you presented looks really neat and convincing although I had a hard time with the notation, since I’m not familiar with it.

    Does the calculational proof works in “all” mathematics?
    Also, could you recommend some literature to get a better grasp on the calculational proofs and maybe on the Eindhoven notation too?

    Thank you and best regards from Slovenia,
    Ted

  2. Ted,

    thanks a lot for your comment. Regarding bibliography, I recommend you to take a look at the following webpage:

    http://twiki.di.uminho.pt/twiki/bin/view/Research/Matisse/MatisseBiblioteca

    It is in Portuguese, but under the section Livros (Books) you can find several good books.
    Also, http://mathmeth.com has some very interesting material and if you google “Dijkstra archive” you’ll find more than 1000 notes from Edsger Dijkstra. I plan to write a post with some references (as this is a frequently asked question), but I don’t know when I’ll do it.

    I don’t really know how to answer to your question “Does the calculational proof works in “all” mathematics?”. There are areas which are much more suitable for calculation than others; all I can say is that our goal is to reduce the amount of guessing and increase the amount of calculation (that way, we believe we can make the teaching of proofs more systematic). I’m currently working more with number theory.

    Finally, you wrote that you had problems with the notation. Could you suggest improvements? What was the most difficult notation and why?

    Thanks again,
    Joao

  3. Pingback: calculational

  4. Pingback: Graph 0 3 | AllGraphicsOnline.com

Leave a Reply to jff Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>