Consider a convex polyhedron in which every face has an even number of edges and every vertex has three faces around it. Can you go for a walk along the edges, coming back to where you started, and passing through each vertex exactly once?


NOTE: this was corrected on July 1 2013 because in my original post I left out one hypothesis. Thanks to the Camp Euclid students for finding the counterexample that showed how much of a mistake I made!

A polyhedron is convex if it has no "dents" in it. More precisely, a polyhedron is convex if, given any two points inside the polyhedron, the entire straight line segment joining those two points is also inside the polyhedron. Now we want to consider a random convex polyhedron with two additional properties: (1) That it's faces all have an even number of edges, a.k.a. sides. (2) That every vertex has three faces around it, or, equivalently, three edges touching it. (Incidentally, any time you read about a problem with a funny extra hypothesis like that, you should immediately wonder why that hypothesis is important. Is it obvious that, when that hypothesis is not satisfied, the answer to the question is, "No"?) The conjecture, due to David Barnette, is that any such polyhedron has what is called a Hamiltonian cycle. A Hamiltonian cycle is a path, starting at a vertex (corner of a face), going around the polyhedron by just walking along the edges, ending back up at the starting vertex, and passing through every vertex exactly once. If you like, think of the vertices as towns and the edges as roads: you want to visit every town exactly once, only travelling along the roads, and get safely back home again at the end. (Of course, starting and ending at home doesn't count as visiting your home town twice.)