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

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ what if $\mathcal C$ contains a set $X$ and also many mutually disjoint subsets? $\endgroup$
    – Fedor Petrov
    Commented Mar 24, 2017 at 6:58
  • $\begingroup$ Right - I should probably exclude $X$. Good point thanks! $\endgroup$
    – Dominic van der Zypen
    Commented 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$
    – Oliver Krüger
    Commented 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$
    – Dominic van der Zypen
    Commented 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$
    – Oliver Krüger
    Commented Mar 24, 2017 at 10:56

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .