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.
