Minimal clique decompositions

Question

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.)

Answer 1

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.

Answer 2

Similar to Ben's answer is an octahedron which is $K_{2,2,2}$ and also $K_6$ minus a matching. There should be an enormous number of minimal covers for other complete multipartite graphs and for $K_{2m}$ with $m$ disjoint edges removed.