# Hamiltonian paths on the space of graphs

Disclaimer: I am not a professional graph theorist.

## Motivation:

Let's consider the set $$G_N$$ of graphs with $$N$$ vertices where the vertices are assumed to be distinguishable. This set may correspond to the state space of a biological network whose connectivity varies over time or the set of potential social networks among a community of $$N$$ individuals.

The cardinality of $$G_N$$ is given by:

$$$$\lvert G_N \rvert = \sum_{k=0}^{ N \choose 2} { { N \choose 2} \choose k} = 2^{{ N \choose 2}} \tag{1}$$$$

I observed that $$\lvert G_N \rvert$$ very quickly becomes astronomical:

$$$$\forall N > 50, \lvert G_N \rvert > 10^{368} \tag{2}$$$$

which is many times greater than the number of atoms in the universe. For this reason, I wondered whether there might be a natural way to organise these graphs. One approach that occurred to me was to think of 'Hamiltonian paths' on the space of graphs.

## Question:

If $$G^k_N \subset G_N$$ denotes the set of graphs with $$N$$ vertices with exactly $$k$$ edges:

$$$$\lvert G^k_N \rvert = { { N \choose 2} \choose k} \tag{3}$$$$

my question is whether we can index the elements of $$G^k_N$$ so we have $$G^k_N = \{\Gamma_i \}_{i=1}^{{ { N \choose 2} \choose k}}$$ and $$\Gamma_i$$ and $$\Gamma_{i \pm 1}$$ differ by at most one edge i.e. all edges are the same except one which is relocated.

We can think of this as a Hamiltonian path because there is an edge between each element of $$G^k_N$$ and each element of $$G^k_N$$ occurs exactly once.

Note: For $$G^k_N$$ where $$k\in \{0,1,{ N \choose 2}-1,{ N \choose 2} \}$$ this proposition is certainly true.

• Hm, this power of 2 counts all graphs, not only planar? Jun 25, 2019 at 9:20
• @FedorPetrov Thanks for pointing this out. Jun 25, 2019 at 9:22
• If you go from one graph to another that “differs in one edge” then they can’t both have $k$ edges, can they? Jun 25, 2019 at 11:26
• @GordonRoyle I just clarified the question. I meant that all edges are the same except one which is relocated. Jun 25, 2019 at 11:33

So you are really asking if there is a Hamilton path through all the $$k$$-subsets of an arbitrary $$\binom{N}{2}$$ set where two sets are adjacent if their symmetric difference has size two.
• Well, it is known that we can move from any unlabelled planar triangulation to any other via a sequence of "edge flips" which are operations where an edge $xy$ is removed, thereby creating a 4-face, say $\mathit{xayb}$, and then the edge $ab$ is inserted, restoring the property of being a planar triangulation. After 30 seconds thought, it seems to me that triangulations will be the hardest to deal with, so I'll put my money on yes. Jun 26, 2019 at 2:31