**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:

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

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

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

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:

\begin{equation} \lvert G^k_N \rvert = { { N \choose 2} \choose k} \tag{3} \end{equation}

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.