1
$\begingroup$

(This is a follow-up to this question.)

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. all members of ${\cal C}$ contain at least $2$ elements, and $X\notin {\cal C}$;
  2. $A\neq B\in {\cal C}$ implies $|A\cap B| \leq 1$; and
  3. 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$

1 Answer 1

1
$\begingroup$

Yes. For any edge $(x,y)$ of a complete graph on $X$ there exists unique set $A(x,y)$ in $\cal C$ containing both $x,y$. Thus if we find a Hamiltonian path in the line graph of $K_m$ (that is pretty easy to do), it produces a Hamiltonian path for $\cal C$.

$\endgroup$

You must log in to answer this question.

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