Three-cuts are a charm : acyclicity in 3-connected cubic graphs

Abstract

Let G be a bridgeless cubic graph. In 2023, the three authors solved a conjecture (also known as the S4-Conjecture) made by Mazzuoccolo in 2013: there exist two perfect matchings of G such that the complement of their union is a bipartite subgraph of G. They actually show that given any 1+-factor F (a spanning subgraph of G such that its vertices have degree at least 1) and an arbitrary edge e of G, there exists a perfect matching M of G containing e such that G\(F∪M) is bipartite. This is a step closer to comprehend better the Fan–Raspaud Conjecture and eventually the Berge–Fulkerson Conjecture. The S4-Conjecture, nowa theorem, is also the weakest assertion in a series of three conjectures made by Mazzuoccolo in 2013, with the next stronger statement being: there exist two perfect matchings of G such that the complement of their union is an acyclic subgraph of G. Unfortunately, this conjecture is not true: Jin, Steffen, and Mazzuoccolo later showed that there exists a counterexample admitting 2-cuts. Here we show that, despite of this, every cyclically 3-edge-connected cubic graph satisfies this second conjecture.