Summary: An equivalence graph is a vertex disjoint union of complete graphs. For a graph G, let eq(G) be the minimum number of equivalence subgraphs of G needed to cover all edges of G. Similarly, let cc(G) be the minimum number of complete subgraphs of G needed to cover all its edges. Let H be a graph on n vertices with maximal degree \(\leq d\) (and minimal degree \(\geq 1)\), and let \(G=\bar H\) be its complement. We show that \[ \log_ 2n-\log_ 2d\leq eq(G)\leq cc(G)\leq 2e^ 2(d+1)^ 2\log_ en. \] The lower bound is proved by multilinear techniques (exterior algebra), and its assertion for the complement of an n-cycle settles a problem of Frankl. The upper bound is proved by probabilistic arguments, and it generalizes results of de Caen, Gregory and Pullman.