## Graph of graphs

The pictures^{1}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.

^{(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).

#### Simple graphs

A graph is called*simple*if it has girth at least 3 (no loops or double edges). It was shown by Coco Zhang

^{2}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;

G(6)

G(8)

G(10)

G(12)

G(14)

G(14,4)

G(16)

G(16,5)

G(18,5)

G(18,6)

G(20,5)

G(20,6)

G(22,6)

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 ↩