1
$\begingroup$

If ${\cal C}$ is a collection of subsets of a set $X$, we associate to ${\cal C}$ a graph $G_{\cal C} = (V,E)$ where $V = {\cal C}$ and $$E = \big\{\{A,B\}: A\neq B\in {\cal C} \land A\cap B \neq \emptyset\big\}.$$

We call ${\cal C}$ full on $X$ if for all $x,y\in X$ there is $A\in {\cal C}$ such that $\{x,y\} \subseteq A$.

Let $G$ be a simple, undirected graph such that for any $2$ distinct vertices, there is a path of length at most $2$ connecting them. Is there a set $X$ and a full collection of subsets ${\cal C}$ on $X$ such that $G_{\cal C} \cong G$?

$\endgroup$
1
$\begingroup$

The answer is no. Let $G$ be the four-cycle $abcd$. Suppose there was a ground-set $X$ and a full family of sets $A, B, C, D$ such that $A$ represents $a$, $B$ represents $b$, etc. Since $ab \in E(G)$, there is some $x \in A \cap B$. As $cd \in E(G)$, there is some $y \in C \cap D$.

  • $ac \notin E(G)$, so $x \notin C$ and $y \notin A$.
  • $bd \notin E(G)$, so $x \notin D$ and $y \notin B$.

Therefore, none of the four sets contains both $x$ and $y$. The family is not full.

$\endgroup$

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.