Hajós' conjecture and small cycle double covers of planar graphs (Q1197036): Difference between revisions

A graph is said to be even if all its vertices have even degree, and it is well known that the edge set of a graph \(G\) can be partitioned into cycles if and only if \(G\) is even. Such a partition of the edges of a graph is called a cycle decomposition of the graph. We let \(c(G)\) denote the minimum number of cycles required in a cycle decomposition of an even graph \(G\). A cycle double cover, \({\mathcal C}\), of a graph \(G\) is a collection of cycles containing every edge of \(G\) exactly twice. If \(G\) has \(n\) vertices, then \({\mathcal C}\) is called a small cycle double cover if it contains at most \(n-1\) cycles. There exist even graphs \(G\) on \(n\) vertices for which \(c(G)\geq\lfloor(n-1)/2\rfloor\), and \textit{G. Hajós} conjectured that every simple even graph \(G\) on \(n\) vertices has \(c(G)\leq\lfloor(n-1)/2\rfloor\). We prove this conjecture for planar graphs (a somewhat incomplete proof was given earlier by \textit{J. Tao}). We then discuss the connection between this result and small cycle double covers of graphs.