# Posts tagged puzzle

## Balloon design and graph theory

Apr 13th

When figuring out balloon designs, it’s optimal to minimize the number of balloons you need and the number of times you break a balloon. This way, you save on the number of balloons you use up, you save time (because breaking balloons and tying knots adds time,) and you save your fingers a little. (Try tying 50 knots and see how your fingers feel!)

Balloon twisting can be used to illustrate some ideas in graph theory. A balloon design can be represented as a graph. The places where the balloon is twisted represent vertices in the graph. The edges in the graph indicate which vertices are connected. For example, the picture below shows a graph of the top of a cake (the pink “frosting.”)

Is it possible to do the frosting with one single balloon without having to break the balloon? (That is the equivalent of asking if this graph has a Euler walk – can all edges in the graph can be visited exactly once?) Take out a pencil and paper and give it a try! See if you can trace over every edge exactly once without picking up your pencil.

Actually, as you’ve probably figured out, it’s not possible. (More than two vertices have an odd degree.) So then, what is the least number of balloon segments necessary to do the frosting, going over every edge exactly once? Can you figure it out?

The next time you are figuring out a balloon design, you might also be solving some equivalent problem of determining the best route for a road trip, package delivery, etc. ðŸ™‚