Return to Revisions

Clearly, if $E'=\{X_1,X_2,\dots,X_n\}$ is the set of all maximal cliques of a simple graph $(V,E)$, then $$E=\binom{X_1}2\cup\binom{X_2}2\cup\cdots\cup\binom{X_n}2.$$ Hence, a necessary and sufficient condition for an antichain $E'$ of subsets of $V$ to be the set of all maximal cliques of a simple graph on the vertex set $V$ is that, for every set $S\subseteq V$, if each $2$-element subset of $S$ is contained in an element of $E'$, then $S$ is contained in an element of $E'$.