Reduction of the Berge-Fulkerson conjecture to cyclically 5-edge-connected snarks
Edita Máčajová, Giuseppe Mazzuoccolo
Abstract
The Berge-Fulkerson conjecture, originally formulated in the language of mathematical programming, asserts that the edges of every bridgeless cubic ( <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="3"> <mml:semantics> <mml:mn>3</mml:mn> <mml:annotation encoding="application/x-tex">3</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -valent) graph can be covered with six perfect matchings in such a way that every edge is in exactly two of them. As with several other classical conjectures in graph theory, every counterexample to the Berge-Fulkerson conjecture must be a non- <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="3"> <mml:semantics> <mml:mn>3</mml:mn> <mml:annotation encoding="application/x-tex">3</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -edge-colorable cubic graph. In contrast to Tutte’s 5-flow conjecture and the cycle double conjecture, no nontrivial reduction is known for the Berge-Fulkerson conjecture. In the present paper, we prove that a possible minimum counterexample to the conjecture must be cyclically <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="5"> <mml:semantics> <mml:mn>5</mml:mn> <mml:annotation encoding="application/x-tex">5</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -edge-connected.