# Terminology for expressing a graph as a sum of cliques (mod 2)

I am interested in the problem of expressing the edges of a given (undirected, simple) graph as the sum of edge sets of cliques modulo $$2$$.

To be more concrete, given a graph $$G=(V,E)$$, I am seeking to find cliques $$C_1=(V_1,E_1)$$, $$\dots$$, $$C_k=(V_1,E_k)$$ so that $$V_i\subseteq V$$ for all $$i$$, each edge set $$E_i$$ consists of all edges between pairs of vertices of $$V_i$$, and (most importantly), every edge $$e\in E$$ lies in an odd number of $$E_i$$ and every non-edge $$e\notin E$$ lies in an even number of $$E_i$$.

For example, in this sense we can express the claw as the sum (modulo $$2$$) of $$K_4$$ and $$K_3$$: (And of course any graph $$G=(V,E)$$ is the sum of $$|E|$$ copies of $$K_2$$, but many graphs have less trivial expressions as sums.)

Have you seen this sort of question asked in the literature? I have not been able to find any terminology for this question, or any literature on it, so I would appreciate almost anything MathOverflow users could share with me about it.

• I'm not sure if this is worthy of a full answer, but there is a similar question about expressing a graph in terms of the symmetric difference of complete bipartite graphs here: mathoverflow.net/questions/76043/… – Christopher Purcell Dec 31 '18 at 17:05

Here is a greedy approach that gives $$\leq |V(G)|-1$$ cliques. Suppose we have some graph $$G$$ that we want to express as a sum of cliques.
Start with an empty graph $$H$$ with $$V(H)=V(G)$$. While $$H$$ is not isomorphic to $$G$$, choose a vertex $$v$$ that has the highest number of "incorrect" (non-)edges, i.e. the highest number of other vertices $$w$$ such that $$vw \in E(H)\triangle E(G)$$ (symmetric difference). Add a clique on the set of vertices $$\{v\} \cup \{ w |vw \in E(H)\triangle E(G)\}$$. Now all of $$v$$'s edges are "correct", and $$v$$ will never be chosen again to appear in a clique.