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 $$S_4$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>S</mml:mi> <mml:mn>4</mml:mn> </mml:msub> </mml:math> -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^+$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> </mml:msup> </mml:math> -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\setminus (F\cup M)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>\</mml:mo> <mml:mo>(</mml:mo> <mml:mi>F</mml:mi> <mml:mo>∪</mml:mo> <mml:mi>M</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> is bipartite. This is a step closer to comprehend better the Fan–Raspaud Conjecture and eventually the Berge–Fulkerson Conjecture. The $$S_4$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>S</mml:mi> <mml:mn>4</mml:mn> </mml:msub> </mml:math> -Conjecture, now a 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.