Graph of graphs

The pictures1 in this page represent the space of trivalent graphs with various number of vertices. This space has a natural geometry, namely, two graphs are close if they differ by a few local mutations.

More precisely, we can give the space of graphs the structure of a graph itself. Let GG(n) be the graph whose vertices are trivalent graph with n=2k vertices and two vertices are connected by an edge if the associated graphs differ by a single Whitehead move.
There are two Whitehead moves possible for every edge.
We are interested in the geometry of this graph. The graph GG(n) is always connected. The number of its vertices is of order n(n/2) (see for example Bollobas) and its diameter is comparable to ( n log n ) (see Rafi-Tao). Here is depiction of GG(6):
The graph GG(6).
The graph GG(n) is natrually stratified by girth.(Recall that girth of a graph is the length of its shortest loop.) Let GG(n,g) be the subgraph of GG(n) consisting all graphs that have girth at least g. Here, we examine if these subgraphs are themselves connected.

Simple graphs

A graph is called simple if it has girth at least 3 (no loops or double edges). It was shown by Coco Zhang2 that the subgraphs GG_simple(n) and GG_not_simple(n) are both connected. Hence to simplify our discussion, we concentrate on simple graphs only. We refer to GG_simple(n) = G(n) and to the subgraph of G(n) consisting of graphs of girth at least g by G(n,g).

Here are a few pictures of the graph of simple graphs. The vertices are colored by the girth of the associated graph as follows:
girth 3: blue;    girth 4: green;    girth 5: cyan;    girth 6: magenta;
At first each strada seem to be connected. On the right, we have the picture of the slice with the same color coding as before.
But for larger values of n this is not true. For n = 18 and 20, the graphs of girth 3 and 4 are omitted to make the picture less crowded.
For n=22, there are 90553 graphs of girth 5. Hence, we just depict the girth ≥ 6 subgraph, which is again disconnected.
It seems like the "end" of G(n) is somewhat tree like. It is a question of McMullen whether this family of graphs is an expander family.

For larger n, the problem becomes computationally more difficult. Here is a table of the number of trivalent graphs of a given girth.3

girth = 3 girth = 4 girth = 5 girth = 6 girth = 7
n = 4 1
n = 6 1 1
n = 8 3 2
n = 10 13 5 1
n = 12 63 20 2
n = 14 399 1018 1
n = 16 3,268 743 48 1
n = 18 33,496 7,350 450 5
n = 20 412,943 91,763 5,751 32
n = 22 5,883,727 1,344,782 90,553 385
n = 24 94,159,721 22,160,335 1,612,905 7,573 1
n = 26 1,661,723,296 401,278,984 31,297,357 181,224 3
n = 28 31,954,666,517 7,885,687,604 652,159,389 4,624,480 21
n = 30 663,988,090,257 166,870,266,608 14,499,780,660 122,089,998 545
n = 32 14,814,445,040,728 3,781,101,495,300 342,646,718,608 3,328,899,586 30,368
  1. 1. These pictures have been produce in collaboration with Roi Docampo and Jing Tao using Sage. Jing Tao's trip to the university of Toronto was funded by the GEAR network.
  2. 2. Coco Zhang is a high school junior at Branksome Hall. This work was done as part of the Math Mentorship Program at the University of Toronto during the winter of 2013.
  3. 3. Source: See also here