Let $G=(V,E)$ be a simple, undirected graph. A *clique decomposition* is a set ${\cal C} \subseteq {\cal P}(V)$ such that


1. $\emptyset \notin {\cal C}$,
2. $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),
3. $\bigcup {\cal C} = V$, and
4. $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.)



Minimal clique decompositions
There can be multiple distinct decompositions of minimum size. Consider a triangular lattice tiling of a torus. The maximal cliques are triangles, so we certainly need $e(G) / 3$ cliques in any minimum-sized clique decomposition. But both the upwards pointing and downwards pointing triangles are a clique decomposition of this size.


