Skip to main content
3 of 5
added 293 characters in body
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Here is a proof of Conjecture 1.

Proof. It suffices to show that if $\mathcal{C}(H) = \mathcal{C}(H)^{{\perp}{\perp}}$, then $H$ has the CK property. First observe that every $S \in \mathcal{C}(H)^\perp$ is a stable set of $H$, otherwise $S$ would intersect some $K \in \mathcal{C}(H)$ in at least two vertices. Now, since $\mathcal{C}(H)^{{\perp}{\perp}}=\mathcal{C}(H)$ it follows that every maximal clique intersects every member of $\mathcal{C}(H)^\perp$ exactly once. Since each member of $\mathcal{C}(H)^\perp$ is contained in a maximal stable set, it follows that every maximal clique intersects every maximal stable set. Thus, $H$ has the CK property.

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187