Dyck's map \(\{3,7\}_ 8\) is a counterexample to a clique covering conjecture (Q920116)

Let c(G) denote the minimum number of cliques necessary to cover all edges of a graph G. If G contains no triangle, then the cliques are the edges of G. In this case removing any edge e must reduce the value of c(G), that is, \(c(G-e)<c(G)\). A counterexample is provided to the following conjecture, communicated by P. Erdős, that states that this is the only situation in which the above inequality holds for all edges of G. Conjecture. If \(c(G-e)<c(G)\) holds for every edge e of a graph G, then G contains no triangle. The counterexample is the underlying graph of the symmetric map \(\{3,7\}_ 8\), obtained from the infinite hyperbolic tessellation of the plane by triangles, 7 at each vertex, by identifying each pair of vertices that are separated by a Petrie path of length 8.