The cages are a class of graphs that I think deserve to be more widely known, because they have a lot of interesting properties that make them useful as counterexamples in graph algorithms and graph theory. They're hard to construct and we don't have a lot of explicit descriptions of them, but that's not so important when you're using one as a counterexample.

First, what is a cage? The cages are parameterized by two numbers, $$r$$ and $$g$$. An $$(r,g)$$-cage is a graph that:

• is $$r$$-regular: each vertex is incident to exactly $$r$$ edges,

• has girth $$g$$: each cycle has at least $$g$$ edges in it, and

• is as small as possible: no graph with fewer vertices is also $$r$$-regular with girth $$g$$.

An example is the Petersen graph, which is the unique smallest $$3$$-regular graph with girth $$5$$ and therefore is also known as the $$(3,5)$$-cage. Another, less well known, is the Robertson $$(4,5)$$-cage. Challenge: find a better layout than Robertson's, below (which I took from Wikipedia and at least shows some hints at symmetry), or than the tangled circular layouts also shown in the Wikipedia article.

I don't think it's obvious that cages exist, for all combinations of $$r$$ and $$g,$$ but they do. They have to be big: A simple argument based on the fact that a breadth first search of depth up to half the girth can't find any cycles shows that these graphs must have $$\Omega(r-1)^{g/2-O(1)}$$ vertices, exponential in $$g$$ even when $$r$$ is bounded. Turning this around, if $$n$$ is the number of vertices in such a graph, $$g$$ can be at most $$2\log_{r-1}n + O(1),$$ only logarithmically small.

Bollobás and Szemerédi ["Girth of sparse graphs", J. Graph. Th. 2002] say that "the first good upper bound" on the size of a cage was by Erdős and Sachs in 1963. I don't know how they proved it (it's in German), but my first guess would be a form of the probabilistic method: random regular graphs have only a small number of short cycles, so probably there's some way of getting rid of them and leaving a remaining regular graph that has none at all. But as far as I know the best bounds are not probabilistic, but instead use the method of Ramanujan graphs, by Lubotzky, Phillips, and Sarnak [Combinatorica 1988]. A Ramanujan graph is a graph whose second eigenvalue is nearly as large as possible, which in turn implies that it is a good expander. In their paper, Lubotzky et al use an algebraic construction to find a family of graphs with $$g = \bigl(\tfrac{4}{3} − o(1)\bigr)\log_{r-1} n$$ and they show that having such a high girth implies that the graph is a Ramanujan graph.

So we know that the girth of a cage is logarithmic in its size. But is the right constant on the logarithm $$2$$ or $$4/3$$? Bollobás and Szemerédi say that it should be $$2$$, and I don't have any reason to doubt it myself. If so, the graphs of Lubotzky et al are not themselves cages, but at least they give us an upper bound on how big cages need to be.

Beyond having high expansion, some of the other properties of cages involve high local symmetry, dense minors and high treewidth, and bad surface embeddings:

• Some of the known small cages are highly symmetric graphs, but there's no particular reason to believe that continues for larger sizes. However, they are locally symmetric: the neighborhood of every vertex looks like every other vertex, out to a radius of half the girth, just a regular tree with no cycles to be seen.

• For fixed values of $$r,$$ a cage is a sparse graph. However, the cages necessarily have much denser minors. To see this, take an arbitrary spanning tree of a cage, and choose a set of equally spaced levels of the tree spaced about $$g/4$$ levels apart, such that there are about $$4n/g$$ vertices in the chosen levels. Contract the tree edges connecting each node with its nearest ancestor in a chosen level (or the root if no such ancestor exists). Because the graph has high girth, these contractions won't produce any self-loops or doubled edges, giving a minor that still has almost as many edges as it did before but with a number of vertices that has been reduced by a logarithmic factor. Even if you delete all but $$(1 + \epsilon)n$$ of their edges, the same argument shows that the remaining graph will still have a dense minor. And because of their high expansion, cages also do not obey anything like the planar separator theorem, and instead have linear treewidth.

• If a graph is embedded on a surface, Euler's formula tells us the genus of the surface as a function of its number of vertices, edges, and faces. For a cage, the number of faces must be very small (each edges is in two faces but each face has logarithmically many edges), from which it follows that the genus must be linear. In fact, the minimum genus for these graphs is very close to the maximum genus of any regular graph with the same degree. They also can't be embedded nicely in the plane: Leighton proved that for bounded degree graphs, the number of crossings in any planar drawing is proportional to the square of the bisection width. Because they are expanders, cages have linear bisection width and quadratic crossing number.

ext_2497288:
2014-03-21T15:46:45Z

I took on the challenge :) After some experimenting I found a way to embed the Robertson graph on a torus by using Hamiltonian cycles. I started with a circular layout. If you take all the edges going round the circle to be one Hamiltonian cycle, then there is another "orthogonal" one made up of edges inside the circle. Using the ordering in each of the cycles as x and y coordinates gives the first layout. The square has periodic boundary conditions (a torus). The x (and y) coordinates of each point are unique (the vertices correspond to the ones in a permutation matrix). The edges belonging to the same Hamiltonian cycle never cross. Note that this is not the only way to connect the vertices like this for these positions. The layout in the square shows that it is possible to get a layout where all the edges are in one of two orthogonal directions. Such a layout is shown in the second image. Again, the parallelogram has periodic boundary conditions. The area of the parallelogram is 9*10-9-8=63. The number of crossings is 63-19=54 and the "density" of points in the grid is 19/63. These layouts do not show the symmetries of the graph, but I think they are interesting nevertheless.

11011110:
2014-03-21T15:52:29Z

Neat, and an interesting style. It reminds me a bit of a style I used for 3-regular graphs in one of my papers. I wonder how much more generally it works. I guess to construct it one needs a Hamiltonian decomposition, which doesn't exist for all 4-regular graphs and may be hard to find.

ext_2497288:
2014-03-21T16:08:52Z

Indeed very similar. I hadn't seen that paper, but what I know about graph drawing is very much based on reading your posts :) You do need the Hamiltonian decomposition. I guess there are many for the Robertson graph, so there will be lots of layouts like the one I showed. It would be interesting to know how many essentially different ones there are. Maybe there are some with more symmetry.

ext_2497288:
2014-03-21T20:24:14Z

I think this graph is the Robertson graph. It has the correct number of vertices and edges. It also is 4-regular and has girth 5. This layout is more symmetrical. The red edges form a cycle of length 12. The whole graph has left/right, up/down and 180 rotational symmetry (each "triangle" keeps its orientation fixed for these transformations). Some of the edges come very close to vertices that they are not incident to. It is best to imagine the five "triangles" simultaneously rotating. The vertices can be labelled as follows.

11011110:
2014-03-21T20:39:09Z

If it is four-regular with 19 vertices and girth 5, then it is definitely the Robertson graph. Not all cages are unique but that one is.

ext_2497288:
2014-03-21T20:53:15Z

I don't know how the original construction works, but the one that this layout is based on is fairly straightforward. Each vertex is labelled (i, j) with i 0, 1, 2, 3 or None and j 0, 1, 2 or None. The label (None, None) is excluded. The edges in Python:

ext_2497288:
2014-03-22T01:42:51Z

The survey article DS16.pdf has a nice symmetric drawing of the Robertson graph using 4 colours and curved edges.