Comptes Rendus
Mathématique

Laura Grave de Peralta and Alexander Kolpakov

Expansion properties of Whitehead moves on cubic graphs

Volume 362 (2024), p. 1825-1836

Online since: 25 November 2024

https://doi.org/10.5802/crmath.691

<figure><img src="image_1.png" /></figure>

This article is licensed under the

CREATIVE COMMONS ATTRIBUTION 4.0 INTERNATIONAL LICENSE.

http://creativecommons.org/licenses/by/4.0/
Research article / *Article de recherche*

Combinatorics, Geometry and Topology / *Combinatoire, Géométrie et Topologie*

# Expansion properties of Whitehead moves on cubic graphs

*Sur les propriétés d'expansion de transformations de Whitehead sur les graphes trivalents*

Laura Grave de Peralta<sup>*a*</sup> and Alexander Kolpakov<sup>*<sup>a,b</sup></sup>

**Abstract.** The present note concerns the "graph of graphs" that has cubic graphs as vertices connected by edges represented by the so-called Whitehead moves. Here, we prove that the outer-conductance of the graph of graphs tends to zero as the number of vertices tends to infinity. This answers a question of K. Rafi in the negative.

**Résumé.** Cette note porte sur le « graphe des graphes », dont les sommets sont des graphes trivalents reliés par des arêtes correspondant aux transformations de Whitehead. Nous montrons ici que la conductance externe de ce graphe tend vers zéro lorsque le nombre de sommets tend vers l'infini. Cela donne une réponse négative à la question posée par K. Rafi.

**Keywords.** Trivalent graph, cubic graph, expander graph, Whitehead move, conductance.

**Mots-clés.** Graphes trivalents, graphes expanseurs, transformation de Whitehead, conductance.

**2020 Mathematics Subject Classification.** 05C48, 05C75, 05C90.

**Funding.** LGdP was supported by the FWO and the F.R.S.-FNRS under the Excellence of Science (EOS) programme project ID 40007542.

Manuscript received 10 March 2024, revised 18 July 2024 and 10 September 2024, accepted 18 September 2024.

## 1. Introduction

The present note is concerned with the graph of connected 3-regular, or cubic, graphs. Such a "graph of graphs" $\Gamma_n$, represents what can be informally described as the "deformations space" of cubic graphs on $2n$ vertices under the Whitehead moves. In particular, we shall investigate its expansion properties.

Let $g$ be a cubic graph (we allow graphs with multiple edges and loops), with set of vertices $V(g)$, and set of edges $E(g)$. Then, for an edge $e \in E(g)$ which is not a loop, there are two possible Whitehead moves $w_e^{(1)}$ and $w_e^{(2)}$ on $e$, depicted in Figure 1, which are local transformations of $g$.

If $e \in E(g)$ is a loop, we define the respective Whitehead moves as having no effect on $g$. Let us note that this convention is not arbitrary. Indeed, we may represent $g$ as a multigraph: a set

<footnote><sup>*a*</sup> Impact Initiatives, 9 Chemin de Balexert, 1219 Geneva, Switzerland</footnote>

<footnote><sup>*b*</sup> University of Austin, 522 Congress Ave., Austin, TX 78701, United States</footnote>

<footnote>*Corresponding author</footnote>
<figure><img src="image_2.png" /><figcaption>**Figure 1.** Two possible Whitehead moves performed on an edge $\epsilon$.</figcaption></figure>

of half-edges incident to vertices and paired by a fixed-point-free involution. Then a Whitehead move does not affect the pairing of half-edges and only changes which vertices the half-edges are adjacent to. If $e$ is a loop, the two vertices $u, v$ adjacent to its half-edges coincide: thus changing the vertex assignment of one of the other two half-edges at $u$ and of one of the other two half-edges at $v$ does nothing.

Let the vertices of $\Gamma_n$ be all possible cubic graphs on $2n$ vertices ($n \ge 1$) up to isomorphism, where two vertices $g_1, g_2 \in V(\Gamma)$ are connected by a directed edge for each Whitehead move $w_\epsilon$, for $\epsilon \in E(g_1)$, such that $w_\epsilon(g_1)$ is isomorphic to $g_2$. It is easy to see that being related by a Whitehead move is an equivalence relation on the set of isomorphism classes of cubic graphs on $2n$ vertices ($n \ge 1$).

In this note, a directed version of this graph of graphs is considered, as it is common to do so in the context of dynamical systems. Moreover, as Whitehead moves are clearly reversible, this choice does not affect the expansion property of $\Gamma_n$.

We introduce the notion of outer-conductance $\phi_{\text{out}}$ because there is no standard definition of expansion for directed non-regular multigraphs, despite them being a natural class of objects to consider.

Outer-conductance captures how easy it is to escape a given subset of the graph. Therefore, having the outer-conductance tend to 0 is a way of saying that the graphs have poor mixing and therefore cannot be “expanders” in this sense.

Namely, we show that the following theorem holds which answers the question about “edge expansion” of $\Gamma_n$ posed by K. Rafi [11].

**Theorem A (Theorem 2).** Let $\Gamma_n$ be the graph of cubic graphs on $2n$ ($n \ge 1$) vertices connected by Whitehead moves. Then $\Gamma_n$ is connected and $\phi_{\text{out}}(\Gamma_n) \to 0$, as $n \to \infty$.

Since $\Gamma_n$ contains loops, it is aperiodic. As a byproduct of this and Theorem 2, we obtain one more statement about the combinatorics of $\Gamma_n$.

**Corollary B (Corollary 4).** For each $n \ge 1$, the graph $\Gamma_n$ is strongly connected and aperiodic. There exists a Perron number $\rho_n$ such that the number of length $\ell$ paths in $\Gamma_n$ is asymptotic to $\text{const} \cdot \rho_n^\ell$, as $\ell \to \infty$.

Finally, in Section 5, we mention some objects connected to $\Gamma_n$.
First and foremost, the graph of graphs is related to moduli spaces of surface triangulations [5, 6] and pants decomposition of surfaces [12], although not entirely equivalent to said objects. The definition considered here is a directed version of the graph of graphs considered in [12], and is quasi-isometric to the latter.

Also, the graph of graphs considered in [12] is quasi-isometric to the “wide” component of the thick part of the moduli space of a genus $g \ge 2$ surface. This means that $\Gamma_n$ describes pants decompositions of the genus $g = n+1$ surface in which the set of separating curves contains only sufficiently short geodesics.

Similar local transformations are considered in [8] and two such pants decompositions represent adjacent vertices in $\Gamma_n$ if they are connected by a (I)-move<fnref n="1" />, while a (IV)-move<fnref n="2" /> is always performed on a handle that corresponds to a loop in the pants decomposition graph, and thus is not taken into account when passing to $\Gamma_n$. In this way, there exists a graph morphism from the directed pants graph to $\Gamma_n$ which sends pants decomposition to their dual graphs, and edges to edges.

As shown in [14, 15], the vertex set of $\Gamma_n$ coincides with the vertex set of the pants graph quotient by the action of the mapping class group. Thus, $\Gamma_n$ is quasi-isometric to the latter.

Thus, knowing the combinatorial properties of $\Gamma_n$ could be useful in the study of the geometric and combinatorial properties of the pants graph.

## 2. Conductance and expansion

Let $G$ be a connected directed graph with vertex set $V(G)$ and edge set $E(G)$. For a subset $S \subset V(G)$, let $d(S)$ denote the sum of vertex out-degrees in $S$, i.e. $d(S) = \sum_{v \in S} d_{\text{out}}(v)$, where $d_{\text{out}}(v)$ is the number of edges of the form $(v, u)$ where $u \in V(G)$. The boundary $\partial(S)$ of a vertex subset $S \subset V(G)$ is defined as the set of directed edges in $E(G)$ joining a vertex in $S$ with a vertex in $V(G) \setminus S$, that is $\partial(S) = \{e = (u, v) \in E(G) \mid u \in S, v \in S^c\}$.

The outer-conductance of $S \subset V(G)$ is defined as follows:

$$ \phi_{\text{out}}(S) = \frac{|\partial(S)|}{\min\{d(S), d(V(G) - S)\}} $$

and the outer-conductance of $G$ is

$$ \phi_{\text{out}}(G) = \min_{S \subset V(G)} \phi_{\text{out}}(S). $$

This is a generalization of the notion of conductance [2, Section 6.2]. Since we work with directed graphs, the definition is adapted so that the volume is measured with respect to the number of out-going edges. By doing so the outer-conductance measures how hard it is to escape a subset of the graph.

As a generalization of the notion of expander families to the case of directed graphs with vertex degrees (both out-degree and in-degree) growing with the number of vertices, we introduce Definition 1.

**Definition 1.** We say that a sequence of directed graphs $G_n$ with out-degree and in-degree growing with the number of vertices is an outer-expander family if the conductance $\phi_{\text{out}}(G_n)$ is uniformly bounded away from 0 as $n$ tends to infinity.

Now we state our main result.

**Theorem 2.** Let $\Gamma_n$ be the directed graph of cubic graphs on $2n$ ($n \ge 1$) vertices connected by Whitehead moves. Then $\Gamma_n$ is connected and $\phi_{\text{out}}(\Gamma_n) \to 0$, as $n \to \infty$. Therefore $\{\Gamma_n\}_{n \in \mathbb{N}}$ is not an outer-expander family.

<footnote n="1">¹Called an A-move in [7]</footnote>

<footnote n="2">²Called an S-move in [7]</footnote>
**3. Proof of Theorem 2**

Let $\Gamma_n$ be the directed graph of (isomorphism classes of) cubic graphs on $2n$ vertices ($n \ge 1$) with edges corresponding to Whitehead moves as defined in the introduction. The following two claims will imply Theorem 2.

3.1. $\Gamma_n$ is connected

This result in mentioned in [11] as attributed to Coco Zhang. We give a proof below by using the
classical facts about tree rotations and rebalancing known in computer science.

<figure><img src="image_3.png" /><figcaption>**Figure 2.** The edge $\epsilon = (v_0, v_1)$ that belongs to a $k$-cycle $C_k$ in $g \in V(\Gamma_n)$ on which a Whitehead move may be performed.</figcaption></figure>

Let $g$ be a cubic graph, and let $C_k$ be an indecomposable $k$-cycle (with $k \ge 2$) in $g$, i.e. an induced cycle subgraph of $g$. If we perform a Whitehead move on the edge $\epsilon$ that belongs to a $k$-cycle $C_k$, a part of which is depicted in Figure 2, we obtain a modified graph (partly) depicted in Figure 3.

<figure><img src="image_4.png" /><figcaption>**Figure 3.** The resulting $(k-1)$-cycle $C_{k-1}$ in $\tilde{g} = w_{\epsilon}(g)$: the edge $\epsilon = (v, w)$ does not belong to $C_{k-1}$.</figcaption></figure>

The overall changes in the structure of $\tilde{g} = w_{\epsilon}(g)$ as compared to $g$ are local and amount to
the following:

* The $k$-cycle $C_k$ has been transformed into a $(k-1)$-cycle $C_{k-1}$;

• If $v_1, w_1$ were part of an $l$-cycle $C_l$ then $C_l$ was transformed into an $(l+1)$-cycle $C_{l+1}$;

* Same applies to any cycle that previously contained $w_0$ and/or $v_0$.

By performing a total of $k-1$ Whitehead moves on the edges in $C_k$, we reduce it to a loop, as depicted in Figure 4. Here we reduced the total amount of $k$-cycles with $k \ge 2$ by one, although the lengths of some other cycles could have been augmented.
<figure><img src="image_5.png" /><figcaption>**Figure 4.** The $k$-cycle $C_k$ ($k \ge 2$) is finally reduced to a loop by $k-1$ consecutive Whitehead moves.</figcaption></figure>

By repeating the above procedure on the remaining $k$-cycles (with $k \ge 2$) of the resulting graph, we shall reduce it to a $(n, b)$-lollipop tree, as defined below, an example of which is depicted in Figure 5. Such a tree has $2n$ vertices and $b = n+1$ loops: note that $b$ is the 1st Betty number of the initial graph $g$, since Whitehead moves preserve the number of vertices and edges of $g$, as well as the rank of $\pi_1(g)$.

<figure><img src="image_6.png" /><figcaption>**Figure 5.** A (2,3)-lollipop tree.</figcaption></figure>

There exists a natural isomorphism between our $(n, b)$-lollipop trees with a chosen loop (i.e. rooted $(n, b)$-lollipop trees with a chosen loop $\varepsilon^*$ as a root), and binary rooted trees. Namely, let us take a rooted $(n, b)$-lollipop tree $(T, \varepsilon^*)$ and remove all the loops as well as the edge $(v^*, v)$ adjacent to $\varepsilon^*$ (with $\varepsilon^*$ being the loop at vertex $v$). The result, $(\tilde{T}, \tilde{v}^*)$ is a binary rooted tree on $2n-1$ vertices with $n$ leaves.

The general theory of binary trees and tree rebalancing [3, Section 12–Section 13] shows that we can bring $(\tilde{T}, \tilde{v}^*)$ to a unique complete rooted binary tree $T_n$ on $n$ vertices by a series of rotations. As Figure 6 shows, a tree rotation can be achieved by a Whitehead move. This proves that $\Gamma_n$ is connected.

## 3.2. *The outer-conductance of Γ<sub>n</sub> tends to 0*

A *bridge* in a connected graph is an edge such that its removal produces several connected components. A graph with a bridge is called *bridged*, while a graph that has no bridges at all is called *bridgeless*.

Let $B_n \subset V(\Gamma_n)$ be the set of (isomorphism classes of) connected cubic graphs on $2n$ vertices that have at least one bridge. We shall estimate the probability $P(g \in B_n)$ asymptotically. For this matter, notice that if $U_n = V(\Gamma_n)$ is the set of unlabelled cubic graphs (i.e. their isomorphism classes), and $L_n$ is the set of labelled ones, then $P(g \in U_n$ has a bridge) = $P(g \in L_n$ has a bridge) + $o(1)$, since according to [1] we have that $|L_n| \sim |U_n| \cdot (2n)!$, as $n \to \infty$.
<figure><img src="image_7.png" /><figcaption>**Figure 6.** A left and right rotation of a rooted binary tree (corresponding to an (n, b)-lollipop tree with root $\epsilon^*$) realised by a Whitehead move on edge $e$. Here $P, Q$ are the vertices of $\epsilon$, and $A, B$, and $C$ are the respective sub-trees</figcaption></figure>

A Hamiltonian circuit in a (connected) graph is a closed edge path that visits each vertex once (i.e. without self-intersection). A graph is called Hamiltonian if it admits a Hamiltonian circuit.

It is clear that a graph that has a bridge cannot be Hamiltonian, and hence every Hamiltonian cubic graph is bridgeless.

Let $\text{Bridged} = \{g \in L_n | g \text{ has a bridge}\}$ and $\text{Looped} = \{g \in L_n | g \text{ has a loop}\}$, and let nH be the set of graphs in $L_n$ that do not have a Hamiltonian circuit. Then

$$ \mathbb{P}(g \in \text{Looped}) \leq \mathbb{P}(g \in \text{Bridged}) \leq \mathbb{P}(g \in \text{Looped}) + \mathbb{P}(g \notin \text{Looped and } g \in \text{nH}), $$

since $\text{Looped} \subseteq \text{Bridged}$, as well as $\text{Bridged} \subseteq \text{nH}$.

By applying [9, Theorem 9.5], we have that $\mathbb{P}(g \in \text{Looped}) = 1 - e^{-1} + o(1)$, while [9, Theorem 9.23] implies that $\mathbb{P}(g \notin \text{Looped and } g \in \text{nH}) = o(1)$, as $n \to \infty$. Thus, $\mathbb{P}(g \in \text{Bridged}) = 1 - e^{-1} + o(1)$ asymptotically, as $n \to \infty$.

Together with the remarks above about the probabilities for labelled and unlabelled graphs, we obtain that $\mathbb{P}(g \in B_n)$, for $g \in V(\Gamma_n)$, satisfies $\mathbb{P}(g \in B_n) = 1 - e^{-1} + o(1)$, as $n \to \infty$. Thus, $|B_n| \sim (1 - e^{-1})|V(\Gamma_n)|$, and $|V(\Gamma_n) \setminus B_n| \sim e^{-1}|V(\Gamma_n)|$.

Note that the only vertices in $B_n$ connected with vertices in $V(\Gamma_n) \setminus B_n$ are those $g \in B_n$ having a single bridge, and the corresponding Whitehead moves have to be performed exactly on the bridge edge of $g$.

Indeed, let $g \in V(\Gamma_n)$ have at least one bridge and let $\epsilon^* = (u, v)$ denote one of its bridges. Then we can check case-by-case what the result of a Whitehead move on $\epsilon^*$ could be.

For this purpose, let us introduce the following equivalence relation on the vertices of $g$: for $v, w \in V(g)$, we write $v \sim_g w$ if and only if there are two edge-disjoint paths connecting $v$ to $w$. Then we write $[v]_g = \{w \in V(g) \text{ s.t. } v \sim_g w\}$ for the equivalence class of $v$.

Let $\{a, b, c, d\}$ be the vertices adjacent to the bridge $\epsilon^* \in E(g)$, and let $\tilde{g} = w_{\epsilon^*}(g)$ be the graph resulting from a Whitehead move performed on $\epsilon^*$. Then we consider the following five possible cases.

(1) $[a]_g = [b]_g = [c]_g = [d]_g$: in this case $\epsilon^*$ is not a bridge neither in $g$, nor in $\tilde{g}$, as shown in Figure 7–Figure 8.
<figure><img src="image_8.png" /><figcaption>**Figure 7.** Local picture inside $g$</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>**Figure 8.** Local picture inside $\tilde{g}$</figcaption></figure>

(2) $[a]_g = [b]_g = [c]_g \neq [d]_g$: same as above, $\varepsilon^*$ is not a bridge neither in $g$, nor in $\tilde{g}$, see Figure 9–Figure 10.

<figure><img src="image_10.png" /><figcaption>**Figure 9.** Local picture inside $g$</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>**Figure 10.** Local picture inside $\tilde{g}$</figcaption></figure>

(3) $[a]_g = [b]_g \neq [c]_g = [d]_g$: in this case, $\varepsilon^*$ is a bridge in $g$, but not in $\tilde{g}$, see Figure 11–Figure 12.

<figure><img src="image_12.png" /><figcaption>**Figure 11.** Local picture inside $g$</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>**Figure 12.** Local picture inside $\tilde{g}$</figcaption></figure>
(4) $[a]_g = [b]_g \neq [c]_g$, $[a]_g = [b]_g \neq [d]_g$, and $[c]_g \neq [d]_g$: again, $\epsilon^*$ is a bridge in $g$, but not in $\tilde{g}$, see Figure 13–Figure 14.

<figure><img src="image_14.png" /><figcaption>**Figure 13.** Local picture inside $g$</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>**Figure 14.** Local picture inside $\tilde{g}$</figcaption></figure>

(5) $[a]_g, [b]_g, [c]_g, [d]_g$ are all distinct: obviously, $\epsilon^*$ is a bridge in both $g$ and $\tilde{g}$, see Figure 15–Figure 16.

<figure><img src="image_16.png" /><figcaption>**Figure 15.** Local picture inside $g$</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>**Figure 16.** Local picture inside $\tilde{g}$</figcaption></figure>

According to the observations above, if a bridged graph $g \in B_n$ can be transformed into a bridgeless one $\tilde{g} = w_\epsilon(g)$, then $\epsilon$ is the only bridge of $g$. Every time, both Whitehead moves either succeed or fail to bring $\tilde{g}$ outside $B_n$. This implies that $|\partial(B_n)| \le 2|B_n|$. Thus the outer-conductance of the set $B_n$ satisfies

$$ \phi_{\text{out}}(B_n) = \frac{|\partial(B_n)|}{\min\{d(B_n), d(V(\Gamma_n) \setminus B_n)\}} \le \frac{2|B_n|}{6n|V(\Gamma_n) \setminus B_n|} \sim \frac{2|V(\Gamma_n)|(1-e^{-1})}{6n|V(\Gamma_n)|e^{-1}} = \frac{e-1}{3n} \to 0, $$

as $n \to \infty$. $\square$

<figure><img src="image_18.png" /></figure>
**Remark 3.** It appears that $\Gamma_n$ is itself a relatively "thin" neighbourhood of $B_n$. Indeed, each length $k$ cycle in a graph $g \in V(\Gamma_n)$ can be reduced by $k-2$ Whitehead moves to a 2-cycle, and one more Whitehead move will create an edge incident to a loop. The standard asymptotic bound on girth is girth($g$) $\lesssim 2\log_2 n$. If $v = |V(\Gamma_n)|$, then $v \sim n^n$ [1], and thus each vertex of $\Gamma_n$ happens to be within $\sim \log_2 \log_2 v$ distance from $B_n$. As shown in [12], the diameter of $\Gamma_n$ satisfies $d = \text{diam}(\Gamma_n) \sim n \log_2 n$, and thus each vertex of $\Gamma_n$ is within $\log_2 d$ of $B_n$.

**4. Combinatorics of paths**

Let $A$ be a non-zero square $k \times k$ ($k \ge 2$) matrix with non-negative integer entries. Such a matrix is called *non-negative*, for brevity. If all the entries of $A$ are actually positive, then $A$ is called *positive*.

If there exists a permutation matrix $P$ such that $PAP^{-1}$ has upper-triangular block form, $A$ is called *reducible*. Otherwise, $A$ is *irreducible*.

For $i \in \{1, \dots, k\}$, the $i$-th period of $A$ is the greatest common divisor of all integers $m$ such that the $i$-th diagonal entry of $A^m$ is positive. If $A$ is irreducible, then all its periods coincide, and each of them equals the period of $A$. If the period of $A$ equals 1, then $A$ is called *aperiodic*.

An aperiodic and irreducible non-negative matrix $A$ is called *primitive*. If $A$ is a primitive matrix, then its spectral radius is a Perron number, as a consequence of the Perron-Frobenius theorem [10, Theorem 4.5.11]. Recall that a *Perron number* is an algebraic integer $\rho > 1$ such that all of its other Galois conjugates have modulus strictly less than $\rho$. Perron numbers often appear in dynamical context, cf. [10]. Another property of the spectral radius of a primitive matrix $A$ is that this eigenvalue has multiplicity one.

Let $\Gamma$ be a directed graph, and let $A$ be its adjacency matrix defined as follows:

$$A_{uv} = \text{the number of directed edges joining } u \text{ to } v, \text{ if } u \neq v,$$

and

$$A_{vv} = \text{the number of loops incident to } v.$$

Then $A$ is irreducible if and only if $\Gamma$ is *strongly connected*, i.e. there exists a path of directed edges in $\Gamma$ between any pair of distinct vertices. If $\Gamma$ is strongly connected and the greatest common divisor of its directed cycle lengths equals 1, then $A$ is aperiodic, and thus primitive. Thus, in this case we can deduce that the spectral radius of $A$ is a Perron number by considering the combinatorics of $\Gamma$.

**Corollary 4.** *The graph $\Gamma_n$ is strongly connected and aperiodic. The number of length $\ell$ paths in $\Gamma_n$ is asymptotic to $\text{const.} \cdot \rho_n^\ell$, with $\rho_n$ a Perron number, if $\ell \to \infty$.*

**Proof.** For every $n \ge 1$, there exists an $(n, b)$-lollipop tree $t \in V(\Gamma_n)$, with $b = n+1 \ge 2$ loops $\epsilon_1, \dots, \epsilon_b$. Then, $w_{\epsilon_i}(t) = t$, for any $i = 1, \dots, b$, and thus $\Gamma_n$ has loops. This implies that $\Gamma_n$ is aperiodic.

**Remark 5.** There exist a 3-cycle and a 4-cycle in each $\Gamma_n$, for $n \ge 3$. Namely, we can choose the cycle in Figure 17. The subgraph of $\Gamma_3$ depicted in Figure 17 embeds in $\Gamma_n$ by replacing the left-most loop in each cubic graph with a sequence of “lollipop” graphs.

Moreover $\Gamma_n$ is strongly connected, as follows from the proof of Theorem 2. Thus, we obtain that $A_n$ is primitive, and can now apply the Perron-Frobenius theorem.

Hence the spectral radius $\rho_n = \rho(A_n)$ is a multiplicity 1 eigenvalue with a positive eigenvector $v$, and $\rho_n$ is a Perron number. Then the asymptotic number of paths follows from [10, Theorem 4.5.12] by a standard computation. $\square$
<figure><img src="image_19.png" /><figcaption>**Figure 17.** Two cycles in $\Gamma_3$ of coprime lengths having a common vertex. Each of them is a cubic graph containing a “lollipop” (a loop incident to an edge) subgraph on the left. By replacing this lollipop subgraph with a lollipop tree on $2n-4$ vertices minus a loop, we obtain a similar picture inside $\Gamma_n$ for every $n \ge 4$ as well.</figcaption></figure>

**5. Related objects**

Above we consider the graph of graphs $\Gamma_n$ of all possible cubic graphs on $2n$ vertices, where two vertices, $g_1, g_2 \in V(\Gamma_n)$, are connected by a directed edge for each Whitehead move $w_\epsilon$, for $\epsilon \in E(g_1)$, such that $w_\epsilon(g_1)$ is isomorphic to $g_2$.

However, there are several ways to modify this definition. Indeed, we could modify the edges of $\Gamma_n$ in order to turn it into an undirected graph, a simple graph or other types of graphs. These modifications can provide relations between the graph of graphs and other mathematical problems. In this section we will explore some of these connections.

**5.1. Matchings on graphs**

Let us consider two edges $e, f$ in $g \in \Gamma_n$ that are not incident to each other. Note that the Whitehead move $w_e^{(k)}(g)$, $k=1,2$, only affects the 4 half-edges incident to the vertices of $e$ (and not belonging to $e$). The same holds for $w_f^{(k)}(g)$, $k=1,2$. Thus, the respective sets of half-edges are disjoint, which implies that $w_e(g)$ and $w_f(g)$ commute. We will call this transformation a *simultaneous Whitehead move on the set* $\{e, f\}$, *cf. [12]*.

Thus, we can consider a modified graph $\Gamma'_n$ with $V(\Gamma'_n) = V(\Gamma_n)$ where $g_1, g_2 \in V(\Gamma'_n)$ are connected by a directed edge if there exists a Whitehead move on some set of non-incident edges of $g_1$ mapping $g_1$ to $g_2$.

Each vertex matching of cardinality $m \ge 1$ in $g_1$ gives rise to $2^m$ simultaneous Whitehead moves. Thus, knowing the number of cardinality $m \ge 1$ matchings in $g_1$ allows us to compute the degree of $g_1$ in $\Gamma'_n$.

**5.2. Outer space and its spine**

Let $F_n$ be the free group on $n \ge 2$ letters. In [4], Culler and Vogtmann introduced a space $X_n$ on which the group Out$(F_n)$ acts. This space can be thought of as analogous to the Teichmüller space of a surface with the action of the mapping class group of the surface.
The description of $X_n$ is complicated, and we will not detail it here. We will only briefly mention the relevant aspects of this object and how it could relate to our graph of graphs.

The space $X_n$ is an infinite, finite-dimensional simplicial complex. A point in $X_n$ is defined as a metric graph (where edges have assigned lengths) of total length 1 with fundamental group $F_n$ equipped with a homotopy equivalence to the bouquet of $n$ circles, called a *marking*. Each open simplex in $X_n$ is obtained by varying the lengths of the edges in a fixed marked topological graph in such a way that their sum remains equal to 1. The group $\text{Out}(F_n)$ acts on $X_n$ by change of markings.

Two given $k$-simplices $x_1$ and $x_2$ share a face of codimension 1 if one can pass from a point in $x_1$ to a point in $x_2$ by collapsing an edge and re-opening it, i.e., by a continuous version of a Whitehead move. Observe that some simplices have missing faces corresponding to loops in the graph, since collapsing a loop would change the fundamental group. Note that simplices of maximal dimension correspond to marked trivalent metric graphs.

The space $X_n$ admits a *spine* $K_n$ which is a deformation retract of $X_n$: the vertices of $K_n$ are marked graphs considered without edge lengths. This spine $K_n$ has the structure of a simplicial complex, in fact it can be identified with the geometric realization of the partially ordered set of open simplices of $X_n$.<fnref n="3" /> The group $\text{Out}(F_n)$ acts on $K_n$ with compact quotient.

Our graph of graphs $\Gamma_n$ is related to $K_{n+1}/\text{Out}(F_{n+1})$ in the following way. Let us consider the dual graph to the collection of top-dimensional simplices in $X_{n+1}$, then take its quotient by $\text{Out}(F_{n+1})$. This will yield a graph that $\Gamma_n$ admits a morphism onto.

## Acknowledgements

Both authors thank the anonymous referees for their comments and suggestions that helped improving the manuscript.

## Declaration of interests

The authors do not work for, advise, own shares in, or receive funds from any organization that could benefit from this article, and have declared no affiliations other than their research organizations.

## References

[1] B. Bollobás, "The asymptotic number of unlabelled regular graphs", *J. Lond. Math. Soc.* **26** (1982), no. 2, pp. 201–206.

[2] F. R. K. Chung, *Spectral graph theory*, American Mathematical Society, 1997, pp. xii+207.

[3] T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, *Introduction to algorithms*, Third edition, MIT Press, 2009, pp. xx+1292.

[4] M. Culler and K. Vogtmann, "Moduli of graphs and automorphisms of free groups", *Invent. Math.* **84** (1986), no. 1, pp. 91–119.

[5] V. Disarlo and H. Parlier, "Simultaneous flips on triangulated surfaces", *Mich. Math. J.* **67** (2018), no. 3, pp. 451–464.

[6] V. Disarlo and H. Parlier, "The geometry of flip graphs and mapping class groups", *Trans. Am. Math. Soc.* **372** (2019), no. 6, pp. 3809–3844.

[7] A. Hatcher, "Pants decompositions of surfaces", 1999. https://arxiv.org/abs/math/9906084.

<footnote n="3">³This is, word for word, the description given in [13].</footnote>
[8] A. Hatcher and W. Thurston, "A presentation for the mapping class group of a closed orientable surface", *Topology* **19** (1980), no. 3, pp. 221–237.

[9] S. Janson, T. Luczak and A. Rucinski, *Random graphs*, John Wiley & Sons, 2011.

[10] D. Lind and B. Marcus, *An introduction to symbolic dynamics and coding*, Second edition, Cambridge University Press, 2021, pp. xix+550.

[11] K. Rafi, *K. Rafi's webpage*, 2024. http://www.math.toronto.edu/~rafi/gofg.html.

[12] K. Rafi and J. Tao, "The diameter of the thick part of moduli space and simultaneous Whitehead moves", *Duke Math. J.* **162** (2013), no. 10, pp. 1833–1876.

[13] K. Vogtmann, "Automorphisms of free groups and outer space", *Geom. Dedicata* **94** (2002), pp. 1–31.

[14] U. Wolf, *Die Aktion der Abbildungsklassengruppe auf dem Hosenkomplex*, PhD thesis, Karlsruher Institut für Technologie, 2009.

[15] U. Wolf, "The action of the mapping class group on the pants complex", 2009. https://www.math.kit.edu/iag3/~wolf/media/wolf-the-action-of-the-mapping-class-group-on-the-pants-complex.pdf.