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



Hamiltonian paths on the space of graphs
If you are talking about labelled graphs (distinguishable vertices) then the fact that these are graphs is irrelevant. 


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.


These are many such Hamilton paths, even Hamilton cycles, known under the general term "combinatorial Gray code".


Look up Carla Savage's survey of combinatorial Gray codes.


