# Walking “withouth gaps” through a set of sets

Let $X\neq \emptyset$ be a finite set and suppose that ${\cal C}$ is a set of subsets of $X$ with the following properties:

1. $X\notin {\cal C}$, and
2. for all $x,y\in X$ there is $A\in {\cal C}$ such that $\{x,y\}\subseteq A$.

Let $m=|{\cal C}|$. Is there a bijection $f: \{1,\ldots, m\}\to {\cal C}$ such that for all $k \in \{1,\ldots, m-1\}$ we have $f(k)\cap f(k+1)\neq \emptyset$?

• what if $\mathcal C$ contains a set $X$ and also many mutually disjoint subsets? – Fedor Petrov Mar 24 '17 at 6:58
• Right - I should probably exclude $X$. Good point thanks! – Dominic van der Zypen Mar 24 '17 at 8:10
• What if $\mathcal{C}$ consists of all the 2-subsets of $X$? Would this then be the same as the problem of finding an Eulerian trail in a complete graph (which is not possible for even $|X| \geq 4$)? – Oliver Krüger Mar 24 '17 at 9:00
• (That's equivalent to saying that $L(K_n)$ does not have a Hamiltonian path, right? In that case, you would be right.) – Dominic van der Zypen Mar 24 '17 at 10:05
• Ah. I see! I misinterpreted it. The line graphs of complete graphs always have Hamiltonian paths - in fact one between every pair of vertices in the line graph. – Oliver Krüger Mar 24 '17 at 10:56

## 1 Answer

Still no. You may choose three subsets which cover all pairs of elements and add many mutually disjoint subsets to this collection.