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$?

  • 1
    $\begingroup$ what if $\mathcal C$ contains a set $X$ and also many mutually disjoint subsets? $\endgroup$ – Fedor Petrov Mar 24 '17 at 6:58
  • $\begingroup$ Right - I should probably exclude $X$. Good point thanks! $\endgroup$ – Dominic van der Zypen Mar 24 '17 at 8:10
  • $\begingroup$ 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$)? $\endgroup$ – Oliver Krüger Mar 24 '17 at 9:00
  • $\begingroup$ (That's equivalent to saying that $L(K_n)$ does not have a Hamiltonian path, right? In that case, you would be right.) $\endgroup$ – Dominic van der Zypen Mar 24 '17 at 10:05
  • $\begingroup$ 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. $\endgroup$ – Oliver Krüger Mar 24 '17 at 10:56

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.