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!

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.

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!

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.