[#P47] Berge-Fulkerson conjecture
Problem. Every bridgeless cubic graph \(G\) has six perfect matchings \(M_1,\ldots,M_6\) such that each edge of \(G\) belongs to exactly two of the matchings.
1Context
The conjecture imposes a highly regular double covering of the edge set by perfect matchings.
2Problem setup
Definition 1 (A cubic graph has degree 3 at every vertex). A cubic graph has degree 3 at every vertex.
Definition 2 (A graph). A graph is bridgeless when deleting any single edge does not disconnect it, and a perfect matching meets every vertex exactly once.
Remark 1. The conjecture imposes a highly regular double covering of the edge set by perfect matchings.
3What counts as a solution
- Construct the required six perfect matchings for every bridgeless cubic graph, or give a bridgeless cubic graph and prove that no such six-match cover exists.
1Status
Current status (Dated status and exact unresolved remainder). Unresolved in this packet after the dated source check. Strongest checked result: The linked 2026 article records a consequence of Kardoš and collaborators: a 1-factor can meet any prescribed collection of pairwise edge-disjoint odd cycles in a bridgeless cubic graph. It treats the six-perfect-matching conjecture as open. Exact unresolved remainder: Construct six perfect matchings covering every edge exactly twice in every bridgeless cubic graph, or give a bridgeless cubic graph and prove that no such cover exists.[1]
1Packet records
Recent contributions
These records are attached to this problem after the current published packet. Each badge shows its current verification or packet-review step.
Notes and companion material
Original intake status. The cited 2026 article treats the Berge-Fulkerson conjecture as a longstanding unresolved conjecture. The source and public status were checked on 2026-07-31. This is an admin-curated seed record, not an independent exhaustive literature review.
- The cycle double cover conjecture was proved in July 2026. That result does not by itself provide the six perfect matchings required here.
Recorded example 1. The complete graph K4 has three perfect matchings. Taking each one twice gives the required six-match cover.
Computational notes
- Perfect-matching enumeration can verify individual graphs and bounded orders.
2See also
- Cycle Double Cover Conjecturegraph theory
- Is there a truly subcubic algorithm for weighted APSP?graph theory
- The Total Coloring Conjecturegraph theory
How to cite
TheoremDB contributors, “Berge-Fulkerson conjecture,” TheoremDB research memory, snapshot of July 31, 2026. https://theoremdb.org/statements/berge-fulkerson-conjectureThis page as plain text: berge-fulkerson-conjecture.md
This problem includes 2 records joined by 2 typed links, sourced from sciencedirect.com[1], current as of July 31, 2026.
1References
- Packet source. Jan Goedgebeur, Giuseppe Mazzuoccolo, Domenico Mattiolo, Jan Renders, Alain Toffanetti, and Carol T. Zamfirescu, On the existence of factors intersecting sets of cycles in regular graphs, European Journal of Combinatorics 135 (2026), 104366. DOI 10.1016/j.ejc.2026.104366. European Journal of Combinatorics 135 (2026), introduction and related conjecture. ↗journal article · primary source · checked 2026-07-31Source use: original summary.The cited 2026 article treats the Berge-Fulkerson conjecture as a longstanding unresolved conjecture. The source and public status were checked on 2026-07-22. This is an admin-curated seed record, not an independent exhaustive literature review.Also cited at abstract, introduction, and discussion of the Berge-Fulkerson consequence.Also cited at Editorial research route recorded 2026-07-31.Source used to formulate or check the problem record.Source used to assess the problem's recorded status.Gives a current neighboring 1-factor theorem while identifying the full six-cover statement as unresolved.Source named by the research packet.
An original CC0 restatement prepared by TheoremDB maintainers.