Math Circle Sesion 12: Eulerian Circuits

Yesterday we turned our attention to Eulerian circuits in math circle. This was a completely “homebrew” session.

We started by asking the children to solve the classical puzzle of drawing this “house” without taking pen off paper, and without retracing your steps.

Screen Shot 2015-05-06 at 20.22.52

Surprisingly, they hadn’t seen it before, but it didn’t take long for them to solve, and also to discover that the path was not unique. We then asked whether it is possible to draw the same shape, following the same rules, but ending up at the end of the drawing back where you started. The children made many attempts at this. Nobody could find a way, but nobody suggested a reason why it wasn’t possible. One child noticed that if you remove the bottom most edge, the problem has a solution.

Screen Shot 2015-05-06 at 20.23.02

As a result, we began to enumerate all the connected graphs with one vertex, with two vertices, with three vertices, and with four vertices. For each graph, children quickly solved the problem where it had a solution. For small enough graphs, where there wasn’t a solution, they could see this through complete enumeration of paths.

One child suggested that there may be a link between the parity of the number of vertices in the graph, and whether or not an Eulerian circuit exists, but I demonstrated this to be false by reference to the two houses – the complete one and the one with the missing floor.

I suggested we look at the act of entering and exiting a vertex, using two edges each time. That, combined with drawing the order on each vertex of each of the graphs we’d enumerated, resulted in the conjecture from one of the kids that Eulerian circuits can only exist when all vertices have even order, and we together constructed an argument why this should be the case.

I then posed the (much harder) converse question: does an Eulerian circuit exist for every connected graph with even order vertices. I am not sure the children clearly understood the difference between this and the previous question; since they had shown that every graph with an Eulerian circuit has even order vertices, I think this seemed “obvious” to them (we must look at logic during one session – any reader with a child-friendly introduction to logic, please let me know!) I asked them to try to produce a graph with even order vertices that does not admit an Eulerian circuit, and they tried for some time before suggesting it is not possible, though none were clear why.

In a step towards trying to answer this question, I wanted to demonstrate that every graph with only even order vertices contains a circuit. I had them first try to construct graphs where each vertex has even order but the graph contains no circuit. Some elaborate failed attempts ensued, but then one child made the following remarkable claim: “it’s possible if the number of vertices is infinite”. I queried this child, and he drew the following “graph”:

Screen Shot 2015-05-06 at 20.19.07

His argument was that all these vertices have order two, yet the graph clearly contains no circuit. I thought this a fairly remarkable construction for a 7 or 8 year old! After restricting ourselves to finite graphs (infinity crops up so often, and absorbs so much interest, we should have a session on infinity also!) we all agreed that every graph with even order vertices contains a cycle.

From that point it was a small step to prove by induction that every graph with even order vertices admits and Eulerian circuit. I think they understood this, but I don’t think I had time to properly emphasise the inductive nature of the proof, and again proof by induction is something we must revisit in the future.

As a final exercise, I had them find an Eulerian circuit in what I had imagined to be a complex case: a pentagram inscribed inside a pentagon, with vertices at all points of intersection. They solved this easily, after which my infinity-inspired child noticed that there is a small pentagon formed by the pentagram, and asked what would happen if we put a pentagram inside this pentagon, and so ad infinitum, forming a fractal graph: would the property still hold?

Lots of things to pick up in future sessions, I think! If I were to change anything when redoing this session, it would be to make the problems more concrete, e.g. using towns as vertices and roads as edges, as my wife had suggested before the session! I think the children “got” it without this, but it might have captured the imagination slightly more.

An Interlude: Is Infinity Odd or Even?

During the session, when infinity came up, I was asked a direct question by one of the younger children: “is infinity odd or even?” At a lull in the main session, I decided we should use this question as a way to talk about the importance of definitions once more. All children had presupposed an arithmetic in which infinity plays the same role as any “other number”, and therefore already had in their minds that, for example, 2 \times \infty = \infty and \infty + 1 = \infty. I didn’t question these suppositions (again – a possible topic for another session!) but instead decided to work with them. I asked for a definition of even, and got:

Definition: A number is even if it is two times a whole number.

I asked for a definition of odd, and got:

Definition: A whole number is odd if it is not even.

To which I added an additional alternative definition:

Definition: A whole number is odd if it is one more than an even number.

Children then quickly worked out for themselves that by their definition (and under their arithmetic) infinity is even. By the first definition of odd, infinity is not odd, but by the second definition, infinity is both odd and even! Thus the two definition of odd coincide for integers but not for their version of arithmetic with infinities. We left that as a talking and discussion point about the importance of definitions, rather than trying to draw any strong conclusions.

One thought on “Math Circle Sesion 12: Eulerian Circuits

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s