Balloons and some graph theory

Balloon riddle

Can you twist the above balloon using just one balloon? (Assume you can’t cut or pop the balloon into more than one segment.)

If you can figure out the above, you are solving a problem equivalent to what the mathematician Euler resolved in 1735, laying the foundations of graph theory!

Seven bridges of Königsberg

Some background: If you are familiar with graph theory, you may remember this as the “Seven Bridges of Königsberg” problem.
At the time, the city of Königsberg, Prussia had 7 bridges connecting its pieces of land that were separated by branches of the Pregel River. The question posed was whether you could walk through the city and cross all bridges, but cross each bridge exactly one time. Euler broke down this problem abstractly. In the below graph, the edges (lines) represent the bridges and the nodes (dots) represent the land the bridges connect.

Graph of the Seven Bridges

Balloon graph

If you compare a graph of the seven bridges of Königsberg with a graph of the balloon (I’ve blogged about graphing balloons before), you’ll see that they are the same. And if you think about it a little more, you may see that asking whether you can cross all the bridges exactly once is the same as asking whether you can twist the above balloon using one balloon!
Pretty cool, huh?!

Balloon twisting has a lot to do with graph theory!

Pac-Man

Another similar question is asking if there’s any route Pac-Man could take to eat all the pac-dots without traversing any part of the maze more than once (assume Pac-Man can start at any point.) Can he?

(Take some time and try to figure it out now!)

The graph representation of this maze is the same as the graphs above. And the question is basically the same question asked before.
Same question, same answer.

(Don’t read below this if you don’t want to know the solution yet.)

Some graph theory basics: if a node (aka vertex) has an odd number of lines coming from it, it is an odd node. If a node has an even number of lines coming from it, it is an even node. Euler proved that if a graph has exactly two odd nodes, you will be able to cross each edge exactly once (there is a Eulerian path), but you have to start at one of the odd nodes and end at the other odd node. If the graph has ALL even nodes, you can cross each edge exactly once AND end at the same point you started (the graph has a Eulerian path AND Eulerian circuit.)

In the graph above, all four nodes are of odd degree, so this graph does not have a Eulerian path or Eulerian circuit. The answer is: you cannot cross all bridges exactly once. And you cannot twist the balloon with exactly one balloon. (You’ll need two balloon segments.) And, no, Pac-Man cannot eat all the pac-dots without traversing part of the maze more than once.

Now back to balloon twisting – I wonder how I can use the above balloon – heart? head of a mouse or koala bear? base of a spaceship? 🙂

(And for you history buffs, two of the seven bridges still exist in what was Königsberg, today Kaliningrad [Russia]. Two of the bridges were damaged by Allied bombing during WWII, a couple were demolished and replaced with a new highway, and one was rebuilt.)