An equivalence relation on a finite vertex set can be represented by an undirected graph that is a disjoint union of cliques. The vertex set represents the elements and an edge represents that two elements are equivalent.
If I have a graph $G$ and graphs $G_1,\dots,G_k$, we say that $G$ is covered by $G_1,\dots,G_k$ if the set of edges of $G$ is equal to the union of the sets of edges of $G_1,\dots,G_k$. The edge sets of $G_1,\dots,G_k$ do not need to be disjoint. Note that any undirected graph $G$ can be covered by a finite number of equivalence relations (i.e., disjoint union of cliques graphs).
I have several questions:
- What can be said about the minimal number of equivalence relations required to cover a graph $G$?
- How can we compute this minimal number?
- How can we compute an explicit minimum cover of $G$, i.e., a set of equivalence relations whose size is minimal and which cover $G$?
- Does this problem has any applications apart from partition logic (the dual of the logic of subsets)?
- Does this problem has a well established name?
Given the various misunderstandings indicated by the comments, here are some pictures to illustrate these concepts. If you have an idea for an easier to understand terminology (instead of "cover", "equivalence relation", "disjoint union of cliques" and "not necessarily disjoint" union of edge sets), feel free to let me know.
Here is a picture of a graph and one equivalence relation covering it:
Here is a picture of a graph and two equivalence relations covering it:
It should be pretty obvious that at least two equivalence relations are required.
Here is a picture of a graph and three equivalence relations covering it:
It's less obvious that at least three equivalence relations are required. Lemma 1.9 from Dual of the Logic of Subsets can be used to show that this is true. The generalization of this lemma to nand operations with more than two inputs was the motivation for this question.