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.
Continue reading

Related Posts:

Multiples in the Fibonacci series

I found the following problem on K. Rustan M. Leino’s puzzles page:

[Carroll Morgan told me this puzzle.]

Prove that for any positive K, every Kth number in the Fibonacci sequence is a multiple of the Kth number in the Fibonacci sequence.

More formally, for any natural number n, let F(n) denote Fibonacci number n. That is, F(0) = 0, F(1) = 1, and F(n+2) = F(n+1) + F(n). Prove that for any positive K and natural n, F(n*K) is a multiple of F(K).

This problem caught my attention, because it looks like a good example for using a result that I have derived last year. My result gives a reasonable sufficient condition for showing that a function distributes over the greatest common divisor and shows that the Fibonacci function satisfies the condition.

In fact, using the property that the Fibonacci function distributes over the greatest common divisor, we can solve this problem very easily. Using $\fapp{fib}{n}$ to denote the Fibonacci number $n$, $m{\nabla}n$ to denote the greatest common divisor of $m$ and $n$, and $\setminus$ to denote the division relation, a possible proof is:

\[
\beginproof
\pexp{\text{$\fapp{fib}{(n{\times}k)}$ is a multiple of $\fapp{fib}{k}$}}
\hint{=}{definition}
\pexp{\fapp{fib}{k} \setminus \fapp{fib}{(n{\times}k)}}
\hint{=}{rewrite in terms of $\nabla$}
\pexp{\fapp{fib}{k} ~\nabla~ \fapp{fib}{(n{\times}k)} ~=~ \fapp{fib}{k}}
\hint{=}{$fib$ distributes over $\nabla$}
\pexp{\fapp{fib}{(k{\nabla}(n{\times}k))} = \fapp{fib}{k}}
\hint{=}{$k{\nabla}(n{\times}k) = k$}
\pexp{\fapp{fib}{k} = \fapp{fib}{k}}
\hint{=}{reflexivity}
\pexp{true~~.}
\endproof
\]

The crucial step is clearly the one where we apply the distributivity property. Distributivity properties are very important, because they allow us to rewrite expressions in a way that prioritizes the function that has the most relevant properties. In the example above we could not simplify $\fapp{fib}{k}$ nor $\fapp{fib}{(n{\times}k)}$, but applying the distributivity property prioritised the $\nabla$ operator — and we know how to simplify $k{\nabla}(n{\times}k)$. Furthermore, in practice, distributivity properties reduce to simple syntactic manipulations, thus reducing the introduction of error and simplifying the verification of our arguments.

(Now that I think about it, perhaps it would be a good idea to write a note on distributivity properties, summarizing their importance and their relation with symbol dynamics.)

If you have any corrections, questions, or alternative proofs, please leave a comment!

Related Posts:

Calculational proofs are usually direct

jd2718 asked in his blog if anyone knew a direct proof of the irrationality of $\sqrt{2}$. In this post I present a proof that, even if some don’t consider it direct, is a nice example of the effectiveness of calculational proof. But first, there are two concepts that need to be clarified: direct proof and irrational number.

Direct proofs

The concept of direct proof can vary slightly from person to person. For instance, Wikipedia defines it as:

In mathematics and logic, a direct proof is a way of showing the truth or falsehood of a given statement by a straightforward combination of established facts, usually existing lemmas and theorems, without making any further assumptions.

Alternatively, in Larry W. Cusick’s website we can read:

A direct poof [sic] should be thought of as a flow of implications beginning with “P” and ending with “Q”.

P -> … -> Q

Most proofs are (and should be) direct proofs. Always try direct proof first, unless you have a good reason not to.

I consider the wording ‘without making any further assumptions‘ in the first definition ambiguous and I don’t understand why the second definition only applies to implications. But anyway, with these definitions in mind, a direct proof for the irrationality of $\sqrt{2}$ can be something like:

\[
\beginproof
\pexp{\text{$\sqrt{2}$ is irrational}}
\hint{=}{justification}
\pexp{true~~.}
\endproof
\]

Or, alternatively, we can also use a proof of the following shape:

\[
\beginproof
\pexp{\text{$\sqrt{2}$ is irrational}}
\hint{\Leftarrow}{justification}
\pexp{true~~.}
\endproof
\]

Irrational numbers

An irrational number is a real number that can’t be expressed as a simple fraction. Therefore, the number $\sqrt{2}$ is irrational because for all integers $m$ and $n$, with $n$ non-negative, we have that:

\[
\sqrt{2} \neq \frac{m}{n} ~~.
\]

A direct proof for the irrationality of $\sqrt{2}$

Now that we have clarified the concepts above, we prove that $\sqrt{2}$ is irrational. For all integers $m$ and $n$, with $n$ non-negative, we have:

\[
\beginproof
\pexp{\sqrt{2} \neq \frac{m}{n}}
\hint{=}{Use arithmetic to eliminate the square root operator.}
\pexp{{n^2{\times}2}\neq{m^2}}
\hintf{\Leftarrow}{Two values are different if applying the same function to them}
\hintl{yields different values.}
\pexp{\fapp{exp}{(n^2{\times}2)} \neq \fapp{exp}{m^2}}
\hintf{=}{Now we choose the function $exp$.}
\hintm{Let $\fapp{exp}{k}$ be the number of times that $2$ divides $k$.}
\hintm{The function $exp$ has two important properties:}
\hintm{$~~~\fapp{exp}{2}=1$ and}
\hintm{$~~~\fapp{exp}{k{\times}l} = \fapp{exp}{k} + \fapp{exp}{l}$}
\hintl{We apply these properties to simplify the left and right sides.}
\pexp{1{\,+\,}2{\times}\fapp{exp}{n} ~\neq~ 2{\times}\fapp{exp}{m}}
\hintf{=}{The left side is an odd number and the right side is an even}
\hintl{number. Odd numbers and even numbers are different.}
\pexp{true ~~.}
\endproof
\]

Note that, unlike traditional proofs, we don’t assume that $m$ and $n$ are co-prime, nor that $\sqrt{2}$ is a rational number. We simply derive the boolean value of the expression $\sqrt{2}~{\neq}~{\frac{m}{n}}$.

If you have any suggestions or corrections, please leave a comment. I’d be more than happy to hear from you.

Note: I learnt the contrapositive of this proof from Roland Backhouse (page 38, Program Construction — Calculating Implementations from Specifications).

Related Posts:

The programmers of tomorrow

A recent article written by Dr. Robert B.K. Dewar and Dr. Edmond Schonberg (both from AdaCore Inc.) is generating some discussion on the state of Computer Science (CS) education in the United States. In “Computer Science Education: Where Are the Software Engineers of Tomorrow?“, Dewar and Schonberg claim that U.S. universities are training unqualified and easily replaceable programmers.

“It is our view that Computer Science (CS) education is neglecting basic skills, in particular in the areas of programming and formal methods. We consider that the general adoption of Java as a first programming language is in part responsible for this decline. We examine briefly the set of programming skills that should be part of every software professional’s repertoire.”

The comment about Java’s adoption annoyed some Java aficionados, but in a recent interview, Robert Dewar adds that the problem goes far beyond the choice of Java as the first programming language. The real problem is that CS programs are being dumbed down, so that they become more accessible and popular. In result, they “are not rigorous enough and don’t promote in-depth thinking and problem solving”.

“A lot of it is, ‘Let’s make this all more fun.’ You know, ‘Math is not fun, let’s reduce math requirements. Algorithms are not fun, let’s get rid of them. Ewww – graphic libraries, they’re fun. Let’s have people mess with libraries. And [forget] all this business about ‘command line’ – we’ll have people use nice visual interfaces where they can point and click and do fancy graphic stuff and have fun.”

Although the paper is concerned with the American reality, I believe we have the same problem in Europe — at least, and as far as I know, in the UK and in Portugal. However, in my opinion, the problem starts before university. The maths’s programs in secondary schools are also being simplified (or dumbed down, if you prefer) and many important concepts, like logic and proofs, are being ignored.

In result, first-year students usually have a poor background on maths and problem solving. In fact, most of them have never seen a proof and don’t even understand the importance of mathematical reasoning. With poor reasoning abilities, they become intellectually less curious, accepting things as they are presented, and they have tremendous difficulties creating new algorithms, or convincing someone that their own algorithms are correct.

Moreover, once they are in the university, one of two things happens:

  1. they are not taught explicitly how to solve problems or how to derive algorithms from their formal specifications (this is the most common case);
  2. or they are taught the above skills but their poor background doesn’t allow them to fully appreciate these subjects.

Continue reading

Related Posts:

A square grid path problem

Last November I have solved Problem 15 of Project Euler (a counting problem involving paths in square grids), and, although the problem admits a simple solution, some of the solutions presented in their forums are very complicated. Thus, I thought it would be a good idea to present my solution, as I consider it very simple.

Problem statement

Starting in the top left corner of a $2{\times}2$ grid, there are 6 routes (without backtracking) to the bottom right corner.

Path diagram for 4×4 square grid

How many routes are there through a $20{\times}20$ grid?

My solution

In order to make the problem more interesting, let us investigate the more general problem of counting the number of routes in an $n{\times}n$ grid. Our argument is based on three observations:

  1. all the paths have size $2{\times}n$ (the reason is obvious: you have to go right $n$ positions and down another $n$ positions);
  2. since we can only go right or down, we can identify every path by a string of Rs and Ds, where a R means going right and a D means going down; as an example, the paths illustrated in the problem statement are (from left to right and from top to bottom): RRDD, RDRD, RDDR, DRRD, DRDR and DDRR;
  3. the strings mentioned above must contain the same number of Rs and Ds.

From these three observations, we can transform the problem to the following:

How many different strings of size $2{\times}n$, consisting of $n$ Rs and n Ds, are there?

The solution is now very simple, because the positioning of $n$ Ds (or Rs) determines the positioning of the other $n$ Rs (or Ds). Hence, the number we are interested in is the number of ways in which we can choose $n$ positions from $2{\times}n$ available positions. The answer, using the traditional notation for the binomial coefficient, is:

\[
{2n \choose n} = \frac{(2n)!}{n! \times n!}~~~~.
\]

Instantiating n with 20, we get the answer to the initial problem of the $20{\times}20$ grid.

Generalization to $m{\times}n$ grids

The generalization to an $m{\times}n$ grid is also simple. The only difference is that the strings have length $m+n$. Using the same reasoning as above, the number of paths through an ${m{\times}n}$ grid is:

\[
{m+n \choose n} = \frac{(m+n)!}{m!\times n!}~~~~.
\]

Final note: If you want to access the forum of the problem, you have to solve it.

Related Posts: