Graphs without \(K_4\)-minors

Hong-Jian Lai 1, Hongyuan Lai2
1West Virginia University Morgantown, WV 26506
2Wayne State University Detroit, MI 48202

Abstract

In [Discrete Math.75(1989)69-99], Bondy conjectured that if \(G\) is a 2-edge-connected simple graph with \(n\) vertices, then \(G\) admits a double cycle cover with at most \(n – 1\) cycles. In this note, we prove this conjecture for graphs without subdivision of \(K_4\) and characterize all the extremal graphs.