Order List of Sets so Adjacent Sets are Disjoint

Question

Let $n \in \mathbb{N}$ and $G := \{1,2,...,n\}$. Now let $P_2(G)$ be a power set of $G$ but only with sets of cardinality $2$, e.g. if $n = 3$ then $P_2(G) = \{ \{1, 2\}, \{1, 3\}, \{2, 3\} \}$.

Now I'd like to order these sets in a list so adjacent sets are disjoint. This only works for $n > 4$.

Furthermore given a partially filled list, I want to be able to increase $n$ and therefore creating more pairs which need to be appended to the end of the list. The existing order of the list cannot be altered. If collisions can not be avoided, they need to be minimal.

e.g. the partial list

({1,2}, {3,4}, {5,1}, {3,2})

for $n = 5$ is given and $n$ is increased by 1:

({1,2}, {3,4}, {5,1}, {3,2}, {6,1}, {3,5}, {6,2}, {1,4}, ...)

Can this problem be solved in polynomial time?

I thought of the following greedy algorithm:

1. pick the least used number that is not a subset of the previous set
2. if there are multiple least used numbers, pick the one that has the highest distance to its last use

Answer 1

You are asking two questions. I will only answer the first. What you are looking for is a Hamiltonian path in the Kneser graph $K(n,2)$.

When $n = 5$, this is the Petersen graph, which contains a Hamiltonian path (though not a Hamiltonian cycle).

When $n \ge 6$, the existence of a Hamiltonian cycle was proved by Heinrich and Wallis, Hamiltonian cycles in certain graphs, using Ore's theorem; in fact, the special case known as Dirac's theorem suffices. Dirac's theorem states that a graph on $N$ vertices with miniimal degree $N/2$ is Hamiltonian (has a Hamiltonian cycle). The Kneser graph $K(n,2)$ contains $\binom{n}{2}$ vertices and is $\binom{n-2}{2}$-regular. A simple calculation shows that $2\binom{n-2}{2} \geq \binom{n}{2}$ when $n \ge 8$, and so $K(n,2)$ is Hamiltonian for $n \ge 8$. Since Ore's theorem has an algorithmic proof, such a Hamiltonian cycle can be constructed efficiently. For the remaining two cases, $n = 6$ and $n = 7$, Heinrich and Wallis give the following Hamiltonian cycles: $$ 25, 16, 23, 45, 12, 34, 56, 13, 24, 35, 46, 15, 26, 14, 36 \\ 25, 37, 12, 34, 56, 17, 23, 45, 67, 13, 24, 35, 46, 57, 16, 27, 36, 47, 15, 26, 14 $$