Cycle covers (III) – Compatible circuit decomposition and K ₅ -transition minor

Let G be a 2-connected eulerian graph. For each vertex v∈V(G), let T(v) be the set of edge-disjoint edge-pairs of E(v), and, T=⋃ _v∈V(G) T(v). A circuit decomposition C of G is compatible with T if |E(C)∩P|≤1 for every member C∈C and every P∈T. Fleischner (1990's) wondered implicitly whether if (G,T) does not have a compatible circuit decomposition then (G,T) must have an undecomposable K ₅ -transition-minor or its generalized transition-minor. This long-standing open problem was partially verified for various graph-minor-free families of graphs, for example, it was solved by Fleischner for planar graphs (Fleischner (1980) [7]) and solved by Fan and Zhang for K ₅ -minor-free graphs (Fan and Zhang (2000) [6]). This transition-minor-free conjecture is now completely solved in this paper. And, as a by-product and a necessary stepping-stone, we characterize the structure of sup-undecomposable K ₅ -minor-free graphs (G,T) in which every compatible circuit decomposition consists of a pair of Hamiltonian circuits. This result plays an important role in the proof of the main theorem and also generalizes an earlier result by Lai and Zhang (Lai and Zhang (2001) [13]).