How are graphs constructed?

Question

I’m reading Nora Hartsfield and Gerhard Ringel’s Pearls in Graph Theory , during introduction on cage, it says ( in 1994) :

“The unique 7-cage is the McGee graph of Figure 4.2.6. The unique 8-cage is the Tutte-Coxeter graph shown in Figure 4.2.7. The 9-cage is not known. There are three distinct 10-cages....”

Seems constructing a graph of a particular property is quite hard! Though 9-cage is known now , according to wiki it has 58 vertices.

I wonder, how would mathematicians start constructing a graph? Surely it can’t rely on luck only , is there any trick ? Or computer could be used to do a brute force search?

Answer 1

Questions from algebraic graph theory are a natural source of such graph constructions. Namely, when you start asking questions about automorphism groups of graphs then you run into these kind of examples or more often counter-examples.

Some examples can be found here: https://en.wikipedia.org/wiki/Graph_automorphism#Graph_families_defined_by_their_automorphisms.

I also recommend reading at least the first few chapters of "Algebraic Graph Theory" by Chris Godsil and Gordon Royle to get a feel for how these famous graphs (again, often constructed as counter-examples) or even whole graph families were constructed by investigating automorphism groups of graphs.

Answer 2

So there are various possible approaches (including, as you say, luck!). To do it by 'brute force' is possible for small cages, even the (3, n) examples you list - McGee, Tutte-Coxeter, the Balaban ones - by just listing all the cubic graphs and then filtering them.

However, as OEIS A005638 shows, the number of cubic graphs on 11 vertices is already 7,373,924. For 14 vertices this becomes 40,634,185,402 which is starting to become time consuming to check. As with all such problems, you can throw more computing resources at it for a while...

Indeed, you have to actually generate these graphs before you can filter them. One way of doing that is outlined here by Brinkmann, Goedgebeur, and Mckay.

A better approach is outlined in this paper by Exoo, McKay, Myrvold, and Nadon. The first basic improvement is to start with the 'skeleton' of the cage - a regular tree - and add edges to that tree to complete the cage. Edges are only added if they are not equivalent to those tried before. This is a 'branch-and-bound' enumeration strategy.

Another approach is to use group theory, which is presumably more efficient still.

See also :

• http://school.maths.uwa.edu.au/~gordon/remote/cages/index.html
• http://oeis.org/A052453