0
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ what if $\mathcal C$ contains a set $X$ and also many mutually disjoint subsets? $\endgroup$ Mar 24, 2017 at 6:58
  • $\begingroup$ Right - I should probably exclude $X$. Good point thanks! $\endgroup$ Mar 24, 2017 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$ Mar 24, 2017 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$ Mar 24, 2017 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$ Mar 24, 2017 at 10:56

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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