Let $G=(V,E)$ be a simple, undirected graph. A clique decomposition is a set ${\cal C} \subseteq {\cal P}(V)$ such that
- $\emptyset \notin {\cal C}$,
- $C\in {\cal C}$ and $x\neq y \in C$ imply that $\{x,y\}\in E$ (that is every member of ${\cal C}$ is a clique),
- $\bigcup {\cal C} = V$, and
- $e=\{x,y\} \in E \implies$ there is $C\in{\cal C}$ such that $x,y\in C$.
Every graph has a clique decomposition (see the collection of all edges plus the isolated points). We call ${\cal C}$ minimal if $|{\cal C}|$ is minimal amongst all clique decompositions of $G$.
Question. If ${\cal C}, {\cal D}$ are minimal clique decompositions of a finite graph $G$, do we have ${\cal C}= {\cal D}$? (The same question could also be considered for infinite graphs, but I guess the answer is no for these.)
