In my Domino Graphs column, I mentioned the Petersen Graph. There, I looked at all the dominoes formed by choosing two numbers from 0 1 2 3 4. Each domino connects to exactly three others, so the graph can be considered cubic -- each node has exactly three edges. The graph is also symmetric -- any of the ten dominoes could be at the center (try it!). The set of words {wiz, two, bet, pub, lip, sly, son, gun, zag, aye} makes the Petersen graph in a different way (how?). Another symmetric graph involves taking the disjoint triples of a 7-set to form the Odd graph O₄. Take 3 different consonants from D L N P R S T in all 35 possible ways. Add vowels to create words, then delete this heptad of words: plus, surd, land, pirn, nest, dept, terl. The resulting object is the Coxeter graph, shown below. Words salt and pond don't share consonants, so they are connected.Words lint and trap share a T, so they are not connected. I used red for T, so I colored the connecting edge for sped and lorn red, since it's the odd man out.

Figure 1. The Petersen Graph and the Coxeter Graph.

Pick your favorite word in the Coxeter graph, and travel around until you get back to your chosen word, without reusing any edges. If your cycle has length 7, you will find that you used seven differently colored paths. (That's the shortest possible cycle, so the Coxeter graph has girth 7). If your cycle has length 8, the edges use 4 colors, each doubled. If your cycle has length 9, you used all seven colors, one tripled. Isn't that amazing? What color combinations happens with cycles of other lengths? From any word, you can reach any other word within 4 steps, so the Coxeter graph has a diameter of 4. Famed geometer HSM Coxeter was a great lover of symmetry -- he liked this graph so much that he wrote a paper about it called simply My Graph. Figure 2 shows different isomorphisms of his graph. If you have a spare set of dominoes laying around, you might find it an enjoyable task to attach the 28 words, and then to plunk them down on each isomorphism. The first two versions are three colored. Notice how every vertex has three different colors. Most cubic graphs can be three-colored -- rare exceptions like the Petersen graph are called snarks. I leave the three-colorings of the other two versions as an exercise.

Figure 2. Different versions of the Coxeter Graph, some three-colored.

When I first started looking at these graphs, I learned of the Foster Census, which is a listing of all of the cubic symmetric graphs up to 768 vertices.  Here's an example of one of them, F64. So far, all the graphs I've shown have had a variety of symmetrical-looking pictures.  I'm certain F64 has a nice picture, but I haven't found it yet.  For almost a year, F90 -- also called the Foster Graph -- was a minor obsession of mine.  I wanted to see it. I moved dots and lines around in all sorts of different ways. I learned many tricks -- computer searches, symmetry finding, line crossings, and hamiltonian paths. Someday, I'll find a nice F64.

Figure 3. F64 in it's raw form.  Puzzle: Make it pretty.

In Figure 1, the Petersen graph's paths cross each other 6 times, and the paths of the Coxeter graph cross each other 15 times. The number of crossings is aptly named the crossing number.  Geoff Exoo has a page showing famous graphs with minimized crossing numbers. The Petersen graph can be drawn with just 2 crossings, and the Coxeter graph with just 11. The Heawood graph can be drawn with 3 crossings. Connect the dots in the figure below with straight lines to illustrate these minimal-crossing representations.

Figure 4. Connect the dots with straight lines to make a Petersen graph and Heawood graph. Answer.

Here are pictures of various cubic symmetric graphs. I found F56A by moving nodes around on my computer screen. I found the outside circle first, and then moved the other nodes close to them.  Suddenly, I saw this very striking figure. I was hooked.

Figure 5. Various Cubic Symmetric Graphs

In 1980, Roberto Frucht, HSM Coxeter, and David Powers developed a method for describing hundreds of zero-symmetric graphs. In the symmetric graphs described on this page, any vertex or edge is equivalent to any other vertex or edge.  In a zero-symmetric graph, the vertices are equivalent, but the edges are maximally dissimilar.  I call their graph description method the Frucht notation. The cubic graph (F8) can be represented as [3,-3]⁴ in Frucht notation. The graph starts with a hamiltonian cycle on the outside.  After that, the vertices are connected by going clockwise 3 spaces, then counterclockwise 3 spaces -- do this 4 times.  F14 is [5,-5]⁷, F16 is [5,-5]⁸, F38 is [15,-15]¹⁹. The raw form of F38 is somewhat long, so you can see why I started liking Frucht notations. F18 is [5, 7, -7, 7, -7, -5]³.  F60 is a bit complicated: [12, -17, -12, 25, 17, -26, -9, 9, -25, 26]⁶.

Figure 6. Cubic Symmetric Graphs with Frucht notations

Many of these graphs are important enough to have specific names. See Eric Weisstein's page on Symmetric Cubic Graphs for a list. One graph that probably deserves a name is F24. Get three different small objects, and put them on 4 different sheets of paper.  You may move any object to the empty sheet.  There are 24 different configurations.  When all the connections are drawn, F24 results.

Figure 7. F24, as a diagram of 3 colored marbles.

After many different computer searches, I hit on [17, -9, 37, -37, 9, -17]¹⁵ --it's the Foster Graph (F90).  I finally got a chance to see it.  I'm glad I searched.

Figure 8. F90 - The Foster Graph

References:

Coxeter, HSM., Frucht, R., Powers, D. Zero-symmetric graphs. Academic Press, 1981.

Coxeter, HSM. "My graph". Proc. London Math. Soc. (3) 46 (1983) 117-136.

Royle, G. Algebraic Graph Theory. Springer, 2001.

Royle, G.  The Foster Census. http://www.cs.uwa.edu.au/~gordon/remote/foster/.  Originally published in 1934 by Ronald M Foster.

Weisstein, E. Symmetric Cubic Graph.  Eric Weisstein's World of Mathematics. http://mathworld.wolfram.com/SymmetricCubicGraph.html

Wolfram, S. A New Kind of Science. Wolfram Media, Inc., Champaign Il, 2002. p 1032.

Many thanks to Stephen Wolfram for asking me to draw F4 to F28, and to Eric Weisstein in maintaining interest in the graphs beyond.

Mathematica Code:

Many of the page at mathworld.wolfram.com have extensive notebooks. http://mathworld.wolfram.com/SymmetricCubicGraph.html is one of those pages.  See also his extensive packages on graph theory at http://library.wolfram.com/infocenter/MathSource/4775/. Anyone who desires my code for Frucht Notation searches, or who finds any, should write me at the address below.

Math Games archives.

Comments are welcome. Please send comments to Ed Pegg Jr. at ed@mathpuzzle.com.

Ed Pegg Jr. is the webmaster for mathpuzzle.com. He works at Wolfram Research, Inc. as the administrator of the Mathematica Information Center.