Skip to main content
added 7 characters in body
Source Link
bof
  • 13.4k
  • 2
  • 43
  • 66

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'$.

Clearly, if $E'=\{X_1,X_2,\dots,X_n\}$ is the set of all maximal cliques of a 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 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'$.

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'$.

Source Link
bof
  • 13.4k
  • 2
  • 43
  • 66

Clearly, if $E'=\{X_1,X_2,\dots,X_n\}$ is the set of all maximal cliques of a 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 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'$.