A simple lower bound on edge coverings by cliques (Q807634): Difference between revisions

The edge clique-cover number c(G) is the minimum number of cliques which cover all edges in the undirected graph G. Call vertices x, y equivalent in the graph G with edge set E if xy\(\in E\) and for all vertices z different from x and y, zx\(\in E\) if and only if zy\(\in E\). In the present paper is proved: if a graph G has n vertices and G contains neither isolated vertices nor equivalent vertices then \(c(G)\geq \log_ 2(n+1)\).