# Posts tagged Math

## Balloons and some graph theory

Mar 23rd

**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.

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.)

## Orderly Tangle

Jan 26th

This is called an “orderly tangle” (or also “regular polylink.”) This particular tangle is made up of four triangles, which when woven together in a certain symmetric fashion form a stable structure. You may have seen tangles in the form of puzzles before. My college roommate was really into puzzles and had a bunch of wooden ones. I first saw tangles that were made from balloons on Vi Hart’s web site.

**To make this balloon**, I used four 260 balloons. I used my neon colors for a cool color combination. I left around a 3-4 inch tail (instead of inflating the entire balloon) as I didn’t want the final structure to be too big/loose. There are no tricky twists – it’s just four triangles. But it is a geometric exercise to figure out how to put it together. You’ll have to make each triangle one at a time as you figure out how to weave them. I added a 5″ round balloon in the middle for fun.

To learn more about these cool geometric structures, check out this video below by George Hart, who has lots of photos and videos of really cool mathematical sculptures at his web site and YouTube channel.

Fin RegPolylinks from Simons Foundation on Vimeo.

## Balloon ball (icosahedron)

Oct 1st

Here’s a balloon ball. Sure, you could just inflate a round balloon, but this is cooler. 🙂

In mathematical terms, it’s actually an icosahedron – a polyhedron with 20 triangular sides. It may look complicated, but because of its symmetry and basic units, it’s actually quite easy to put together. I first saw this on Vi Hart’s web site, where she has posted great instructions for this icosahedron, as well as many other mathematical shapes, such as fractals, tangles, and other polyhedra! Check it out!

**To make this balloon**, I took three 160 balloons and cut each in half. Each section was then used to make one of the six units. (I wanted to make an icosahedron that wasn’t too big.)

If you’d like to read a mathematical paper written about balloon twisting, check out: Computational Balloon Twisting Theory: The Theory of Twisting Polyhedra, co-authored by Hart, Martin Dermaine, and Erik Dermaine (who was one of my college professors!)

## 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. 🙂