I have always enjoyed decorating my home with Christmas lights. I think I enjoy the planning process even more than actually stringing the lights.

I recently moved into a new house with a truss over the front door. Of course, I wanted to outline the truss in Christmas lights. Was there a way to light each piece of the truss without doubling back?

Could I light that up like this:

I tried all sorts of patterns, starting at various places and I seemed to be able to get close. I sometimes thought I had figured it out, only to find I had doubled back, or left out one beam. I began to suspect there was no solution.

Then, I remembered what I had learned decades ago about graph theory in my Introduction to Algorithms and Data Structures computer science course (thanks, @BrownCSDept!), and more recently, my work with graphs in the Oracle database. My Christmas light problem is similar to drawing a figure without removing the pencil from the paper. So, I Googled “draw a polygon without lifting the pencil” and came across a video by Beth at Tom Rocks Maths. Well, the video points out that my shape is not “traversable” and what I wanted to do cannot be done! That’s because there are more than two vertices with an odd number of edges (see below).

An Eulerian path is only drawable without lifting the pencil (equivalent to not doubling back) if it has zero or two vertices with an odd number of edges (or “degrees”). The two odd vertices are where you begin and end drawing. I have four vertices with an odd number of edges (3, 3, 3, 5). Bummer. Also, to have a hope of lighting this up, I would have to start (and end) with the vertex that has an odd number of edges.

Thanks, Euler, for succinctly framing the issue, and thanks, Tom Math Rocks, for explaining this so well!

Euler’s work pointed to two potential solutions: 1) use two different paths—I get two pairs for each path—or 2) convert two of the odd vertices by adding an extra line between those two vertices.

For solution 1, I split the truss into a left and a right half. Each circuit gets two pairs of odd-numbered vertices. In the lighting world, that means using two different strands of lights, so I get two beginnings and two ends. In the below solution, I use one light strand for the left side of the truss and another light strand for the right side.

For solution 2, I start at the upper left vertex, and continue around the truss, and end up re-tracing the shortest edge to minimize the double-back distance. I can finish the vertical edge. Perhaps by using burnt-out bulbs or by somehow running the lights *behind* the truss I can hide that extra line.

So…if I use multiple light strands, or double back once (maybe using burnt out bulbs), I can light up the truss!

I ended up going with solution 2, mostly because I could not find light strands short enough. Also, it seemed unlikely that I could find two light strands of different lengths, but equal brightness.

Here’s the picture of the completed lit truss:

If you look closely, you can see the burnt-out bulbs I used when doubling back in the top right edge.

What makes graph theory so powerful is the way problems can be abstracted and solutions can be found to entire classes of problems. This same technique can be used for all sorts of mathematical (and real-life business) problems such as planning snow plow and trash collection routes.

If you like this type of problem, check out the Wikipedia article about the Seven Bridges of Konigsberg that inspired Euler to invent Graph Theory and the subsequent Chinese Postman Problem that discusses minimizing the length of the edges that are traveled twice.