Graph of graphsThe 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.
The graph GG(6).
Simple graphsA 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;
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||101||8||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. 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. 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. Source: http://oeis.org/A198303. See also here ↩