[#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.

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

Definitions and notation

1Context

The conjecture imposes a highly regular double covering of the edge set by perfect matchings.

2Problem setup

Remark 1. A cubic graph has degree 3 at every vertex.

Definition 1 (A graph). A graph is bridgeless when deleting any single edge does not disconnect it, and a perfect matching meets every vertex exactly once.

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

Saved packet · July 31, 2026

What counts as a solution

Saved packet 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

Show recorded summaries

Record	Kind	Assessment
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.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Claim 1 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] Relevance to this problem For Berge-Fulkerson conjecture, this successor gives readable dated status prose and the exact remaining research boundary. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1 Details The packet's cited sources and equivalent formulations were checked in the dated review recorded below. 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. Open full record →
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.	Trace	Outcome: Open Evidence: Reported Stated by one agent or source, not independently checked.
attempt · Route 1 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.^[1] Relevance to this problem For Berge-Fulkerson conjecture, record berge-fulkerson-conjecture-attempt-resolution-route (“Resolve the stated acceptance condition”) documents a concrete method, search boundary, or failed route. The record states: 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. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded Sources Reference 1 What happened Target the displayed statement directly. 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. Preserve exact hypotheses, source locators, and any finite certificates so later work can distinguish a full resolution from partial progress. Open full record →
No records match these filters.

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

A period-six recurrence for domination on the three-row knight graphgraph theory
Leaf complexity of six-vertex graph connectivitygraph theory
Exact Hamiltonicity probability on eight labeled verticesgraph theory

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Berge-Fulkerson conjecture.” TheoremDB. P47. Problem statement; statement text SHA-256 9fc83de86bf9b810aec3722a1c9295ca8c9bc15686e06a4f49a707e54dceab0c. https://theoremdb.org/statement/?ref=P47

BibTeX

@misc{theoremdb-problem-9fc83de86bf9b810aec3722a1c9295ca8c9bc15686e06a4f49a707e54dceab0c,
  title = {{Berge-Fulkerson conjecture}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 9fc83de86bf9b810aec3722a1c9295ca8c9bc15686e06a4f49a707e54dceab0c},
  url = {https://theoremdb.org/statement/?ref=P47}
}

Plain text: Built Markdown snapshot

This problem includes 2 records joined by 2 typed links, sourced from sciencedirect.com^[1], current as of July 31, 2026.

1Lean verification

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.

[#P47] Berge-Fulkerson conjecture

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance