Train tracks and graph theory

I think games and toys, even those for young children, can often be a great source of interesting mathematics.  Recently a friend of mine was helping his sons build a train track using the pieces shown below:

An unfinished train track, with all available track pieces shown.

An unfinished train track, with all available track pieces shown.

As you can see, this particular track is “incomplete”: one track segment has an end that is not interlocked (in jigsaw-puzzle fashion) with any other piece.  Let’s say that a track is complete if it doesn’t have this problem; that is, every piece used has each of its puzzle-piece “ends” interlocked with some other piece in the track.

My friend wondered whether it was possible to build a complete track, using all of the available pieces shown in the photo?  It turns out that it is not possible… and so the next question is, how to prove it?

This problem has a flavor very similar to the so-called mutilated chessboard, in that (1) it seems difficult at first glance to prove that you can’t do something, no matter how hard you try; and yet (2) thinking about the problem in just the right (but not necessarily obvious) way yields a straightforward proof.

In this case, suppose that we view a complete track as a graph, consisting of vertices (drawn as points) and edges (drawn as line segments connecting pairs of vertices).  Each track piece is a vertex, and an edge between vertices indicates that the corresponding track pieces are interlocked, as shown below, with vertices in blue and edges in green:

The corresponding graph, with each vertex (blue) representing a track piece, and each edge (green) representing an interlocking connection between pieces.  The dashed yellow edge would complete the track/graph.

The corresponding graph, with each vertex (blue) representing a track piece, and each edge (green) representing an interlocking connection between pieces. The dashed yellow edge would complete the track/graph.

If a track is complete, then every possible connection has an edge associated with it.  Let us temporarily suppose that the track shown above is actually complete, that the “three-way switch” piece is actually a four-way switch, and that the extra dashed yellow edge represents the final required connection.

Now, given such a graph representing a complete track, how many edges does it have?  We could just count up the green and yellow line segments, and find that there are 49 edges… but instead, let us examine each vertex v in turn, computing its degree d(v), or the number of edges emanating from it.  We will see why this is handy shortly.

Most of the vertices, corresponding to the simple track segments with two ends, have degree 2.  But some of the “switch” track pieces have degree 3, and one of our temporarily-augmented pieces now has degree 4.  If we add up the degrees of all of the vertices, we find that the total in this case is 98… exactly twice the number of edges!

This is no coincidence.  In general, given any undirected graph, the sum of its vertex degrees equals twice the number of edges.  To see why, consider that in the summation, each edge in the graph gets “counted” exactly twice, once for each of its two vertex endpoints.

An immediate corollary is that, in any such graph, the sum of the vertex degrees must be even.  And this leads to the desired result: if we expect to have any chance of using all available track pieces to build a complete track, then the sum of the degrees– i.e., total number of interlock points– of all of the pieces must be even.  But as shown in the original photo above, in addition to the simple track segments with degree 2, there are five pieces with degree 3, yielding an odd total.

 

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s