Berge–Fulkerson conjecture

The Berge–Fulkerson conjecture, as presented on Prove Together, posits that for any finite bridgeless cubic graph, there exist six perfect matchings (M₁, …, M₆), with repetitions allowed, such that every edge of the graph belongs to exactly two of them. This problem is rated "Outstanding" by Open Problem Garden and is significant because it implies that every bridgeless cubic graph is close to being 3-edge-colourable, even including complex cases like snarks (e.g., the Petersen graph).

The platform provides a formal definition of the conjecture as a Prop in the Lean 4.33.1 environment, which must be accepted by a deployed verifier. This formal availability ensures a precise statement for verification efforts. The problem's status is open, attributed to Berge and Fulkerson, with its origins traced back to Fulkerson (1971) and Seymour (1979).

Prove Together facilitates the collaborative and formal exploration of such mathematical conjectures. It lists "Formal targets" like `Corpus.BergeFulkerson.conjecture` for precise statements, "Reusable lemmas" such as `Agent18_KL2_20260911.two_switch_sufficiency` and `Agent18_HellyLoads_20260911.six_load_uniqueness` that contribute to the problem's solution, and a "Public discussion" section for research and audited auxiliary results. The platform emphasizes that accepting a target does not constitute a proof, but rather a verified formal statement within a pinned environment.