Theorem 34: Hall’s marriage theorem

I was recently given a box of chocolates.  This was a very nice surprise, but closer inspection revealed that I don’t like all of the flavours in the box.  There were twelve chocolates, and I like six of them.  I thought that perhaps I could invite some other people to share the chocolates with me, hoping that they’d take the ones I don’t like.  Naturally, if I do that I have to make sure that everyone gets one chocolate each, to be fair.  But I expect that some of them will like only certain chocolates too.  So I thought that I’d ask eleven people which of these chocolates they like.  That would give me twelve lists of acceptable chocolates (including my own).  But will I be able to assign chocolates to people so that everybody gets a chocolate they like?  If not, I’ll have to revise my guest list.

Well, I could try assigning theoretical chocolates to people in advance, to check.  But that sounds terribly time-consuming.  Is there some easy way in which I could tell whether it will be possible?  Are there any circumstances in which I could immediately tell that it would be impossible?

Theorem 8: Eulerian circuits

On several occasions over the last few weeks, I have read that Immanuel Kant was from the Prussian city of Königsberg (now Kaliningrad in Russia).  As a mathematician, this is not the first thing that comes to mind when I think of Königsberg. Instead, I think of the famous seven bridges (no longer all there), and the mathematical problem that they inspired.  Let me tell you about that problem, and about some of the interesting mathematics that came out of it.

Like many cities, Königsberg was situated on a river.  The city included an island in that river, and so there were several bridges, between the island and the banks of the river.  There’s a picture of the city and its bridges on Wikipedia.

So what was the problem?  Well, could a resident of Königsberg have gone for a Sunday afternoon stroll in such a way that he would walk over each bridge exactly once? That is, he had to cross every bridge (no doubling back!), but he wasn’t allowed to walk across any bridge more than once. (No ferries allowed either!)  Oh, and our friendly Königsberger wanted to end up at home, where he started.

The problem was first solved by the great Swiss mathematician Leonhard Euler.  What did he do?  His first step was to strip away the extraneous information so that he could focus on the important things.  Today, we are familiar with his idea, thanks to the map of the London underground, but of course that came much later than Euler.  The idea is the same, though: what matters is not geographical locations, but which places are joined to which other places.  We can represent lumps of land (the island and the banks of the river) by blobs (vertices, singular vertex), and bridges by lines connecting those blobs (edges).  Here’s what Königsberg looks like when represented in this way (by a graph).

Now the problem is to decide whether we can draw this network of edges without taking the pen off the paper (and without drawing any edge more than once).  You might like to try this before reading on.