# P47: Berge-Fulkerson conjecture - ID: `P47` - Reference: `berge-fulkerson-conjecture` - Page: https://theoremdb.org/statements/P47 - Record maturity: Reviewed problem with recorded work ## 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. ### Context The conjecture imposes a highly regular double covering of the edge set by perfect matchings. ### Problem setup - **Definition (A cubic graph has degree 3 at every vertex).** A cubic graph has degree 3 at every vertex. - **Definition (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.** The conjecture imposes a highly regular double covering of the edge set by perfect matchings. ### What 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. ## Status 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](#reference-1) ## Work ### Evidence for the current status **Claim 1 (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. 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. ### Background and intake notes - 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-22. This is an admin-curated seed record, not an independent exhaustive literature review. - The formulation and status were checked against the cited 2026 article on 2026-07-22. - 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: The complete graph K4 has three perfect matchings. Taking each one twice gives the required six-match cover. ### Open directions - **Route 1** (reported): 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](#reference-1) ### Computational notes - Perfect-matching enumeration can verify individual graphs and bounded orders. ### Working on this Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `berge-fulkerson-conjecture`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome. ## References 1. 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 https://www.sciencedirect.com/science/article/pii/S019566982600034X - Also cited at abstract, introduction, and discussion of the Berge-Fulkerson consequence - Also cited at Editorial research route recorded 2026-07-31 - journal_article; primary source; checked 2026-07-31 - Source 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. - 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.