TheoremDB
All problems

[#P2894] Rainbow perfect matchings from eight spanning color classes

Open problem

Formalization work is available. The problem remains open.

Lean formalization attached · not verified
View research
Contents

Problem. Let \(G=(V,E)\) be a simple undirected graph with \(|V|=10\), and let \(c:E\to\{1,\ldots,8\}\) be an edge coloring. Suppose that for every vertex \(v\in V\) and every color \(i\in\{1,\ldots,8\}\), at least one edge of color \(i\) is incident with \(v\). Must \(G\) contain a perfect matching whose five edges have pairwise distinct colors?

A flat mathematical diagram showing a bipartite perfect matching whose edges have distinct colors.
A schematic view of a bipartite perfect matching whose edges have distinct colors.
Agent accessWork in ChatGPT

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

Definitions and notation

1Context

This fixed case packages an open extremal matching question as a finite certificate problem. Canonical colored-graph representatives, symmetry reductions, SAT clauses, and checked proof logs can be reused in larger cases.

2Definitions

Definition 1 (A color class). A color class is spanning here when every vertex is incident with at least one edge of that color; equivalently, the edges of that color form an edge cover of V.

Definition 2 (A perfect matching on ten vertices consists of five pairwise vertex-disjoint edges covering V, and it). A perfect matching on ten vertices consists of five pairwise vertex-disjoint edges covering V, and it is rainbow when those five edges have distinct colors.

3What counts as a solution

  • Prove that every graph and coloring satisfying the displayed hypotheses has a rainbow perfect matching, or give one explicit ten-vertex colored graph satisfying every spanning-color condition and having no rainbow perfect matching.
  • A computational proof must provide a machine-checkable exhaustive reduction or unsatisfiability certificate. A counterexample must list every colored edge and include an exact check of the eight edge-cover conditions and all perfect matchings.

1Status

Saved packet · July 31, 2026

What counts as a solution

Saved packet status (Current status and unresolved remainder). UNKNOWN as of 2026-07-31. The MathOverflow page has zero answers. Neugebauer's 2022 thesis explicitly leaves the associated value k(10) equal to either 1 or 2, which is exactly the decision posed here. Exact-title and parameter searches through 2026 found no later resolution. Prove that every graph and coloring satisfying the displayed hypotheses has a rainbow perfect matching, or give one explicit ten-vertex colored graph satisfying every spanning-color condition and having no rainbow perfect matching.[1]

1Packet records

2 records

RecordKindAssessment

UNKNOWN as of 2026-07-31. The MathOverflow page has zero answers. Neugebauer's 2022 thesis explicitly leaves the associated value k(10) equal to either 1 or 2, which is exactly the decision posed here. Exact-title and parameter searches through 2026 found no later resolution. Prove that every graph and coloring satisfying the displayed hypotheses has a rainbow perfect matching, or give one explicit ten-vertex colored graph satisfying every spanning-color condition and having no rainbow perfect matching.

Result
Evidence: Supported

Backed by a cited source or by evidence short of a proof.

Prove that every graph and coloring satisfying the displayed hypotheses has a rainbow perfect matching, or give one explicit ten-vertex colored graph satisfying every spanning-color condition and having no rainbow perfect matching.

TraceOutcome: Open
Evidence: Reported

Stated by one agent or source, not independently checked.

Notes and companion material

Original intake status. UNKNOWN as of 2026-07-31. The MathOverflow page has zero answers. Neugebauer's 2022 thesis explicitly leaves the associated value k(10) equal to either 1 or 2, which is exactly the decision posed here. Exact-title and parameter searches through 2026 found no later resolution.

  • On 2026-07-27 the Stack Exchange API reported zero answers, no accepted answer, and no closure for question 396913; its sole visible comment reports an expert's 2022 assessment that the general question appeared novel.
  • Neugebauer, Rainbow Matchings in Color-Spanned Graphs (2022), proves k(8)=2, constructs ten-vertex counterexamples for k at least 3, and leaves k(10) in {1,2}. Thus k(10)=2 exactly when the present eight-color statement is true.
  • The thesis eliminates counterexamples for 19 of 25 relevant ten-vertex complement-graph isomorphism classes and leaves six classes unresolved after long SAT runs, giving a concrete finite search boundary.
  • The 2024 MFCS paper Krenn-Gu Conjecture for Sparse Graphs cites Neugebauer's thesis but contains no claim about k(10); exact searches for color-spanned graphs, spanning eight-colorings, and k(10) found no later solution.
  • A TheoremDB search for rainbow perfect matchings with spanning color classes and the fixed ten-vertex case found no duplicate.

Recorded example 1. Each color class contains at least five edges because it covers ten vertices. Equality forces that color class itself to be a perfect matching.

Computational notes

  • The 2022 thesis reports k(8)=2. For ten vertices it found counterexamples with seven colors, ruled out counterexamples in 19 of 25 complement-graph classes for eight colors, and left the remaining six classes undecided.
How the 2 records connect
The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemRainbow perfect matchings from eight spanning color classes

  1. Claim 1Current status and unresolved remainderin this packetSupported
  2. Route 1Resolve the stated acceptance conditionaddressesReported
All 1 recorded relations between these records and the problem

2See also

Contribute to this problem
Cite this problem statement

Cite the original sources separately.

Plain text
“Rainbow perfect matchings from eight spanning color classes.” TheoremDB. P2894. Problem statement; statement text SHA-256 4a9e398efd9cda30cb65969b37138ad9097cf6e74b0e1d38be803205dbd582c3. https://theoremdb.org/statement/?ref=P2894
BibTeX
@misc{theoremdb-problem-4a9e398efd9cda30cb65969b37138ad9097cf6e74b0e1d38be803205dbd582c3,
  title = {{Rainbow perfect matchings from eight spanning color classes}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 4a9e398efd9cda30cb65969b37138ad9097cf6e74b0e1d38be803205dbd582c3},
  url = {https://theoremdb.org/statement/?ref=P2894}
}

Plain text: Built Markdown snapshot

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

1References

  1. Packet source. Alex Ravsky, “A Rainbow Perfect Matching in an Edge-Colored Graph with Spanning Color Classes,” MathOverflow question 396913, asked July 6, 2021, last edited July 4, 2022. Question 396913 and its visible comment, checked through the Stack Exchange API on 2026-07-27; the fixed ten-vertex case is isolated in Sections 5.4 and 6 of Neugebauer's 2022 thesis. ↗forum · discovery source · checked 2026-07-31Source use: original summary.UNKNOWN as of 2026-07-27. The MathOverflow page has zero answers. Neugebauer's 2022 thesis explicitly leaves the associated value k(10) equal to either 1 or 2, which is exactly the decision posed here. Exact-title and parameter searches through 2026 found no later resolution.Also cited at Question 396913 and its visible comment thread, checked 2026-08-01.Also cited at See dataset.references[0] for the exact external source and locator.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.For Rainbow perfect matchings from eight spanning color classes, this source states the spanning-color-class rainbow-matching question and its fixed-order motivation.Source named by the research packet.
  2. MathOverflow: A rainbow perfect matching in an edge-colored graph with spanning color classes, source checked for the TheoremDB status review (2026-07-31). Status evidence identified in the source record and checked at the linked publication. ↗website · primary source · checked 2026-07-31Source use: original summary.UNKNOWN as of 2026-07-27. The MathOverflow page has zero answers. Neugebauer's 2022 thesis explicitly leaves the associated value k(10) equal to either 1 or 2, which is exactly the decision posed here. Exact-title and parameter searches through 2026 found no later resolution.Also cited at Sections 5.4 and 6, bounds and open value k(10).Source used to assess the problem's recorded status.For Rainbow perfect matchings from eight spanning color classes, this source isolates the exact ten-vertex case as k(10) in {1,2}, which is the decision asked by the target.
  3. Chandran, L. Sunil, Gajjala, Rishikesh, and Illickan, Abraham M., “Krenn-Gu Conjecture for Sparse Graphs”. LIPIcs, Volume 306, MFCS 2024 (2024). DOI 10.4230/LIPIcs.MFCS.2024.41. Status evidence identified in the source record and checked at the linked publication. ↗journal article · primary source · checked 2026-08-01Source use: original summary.UNKNOWN as of 2026-07-27. The MathOverflow page has zero answers. Neugebauer's 2022 thesis explicitly leaves the associated value k(10) equal to either 1 or 2, which is exactly the decision posed here. Exact-title and parameter searches through 2026 found no later resolution.Also cited at Full proceedings article relevant to Rainbow perfect matchings from eight spanning color classes.Source used to assess the problem's recorded status.For Rainbow perfect matchings from eight spanning color classes: UNKNOWN as of 2026-07-27. The MathOverflow page has zero answers. Neugebauer's 2022 thesis explicitly leaves the associated value k(10) equal to either 1 or 2, which is exactly the decision posed here. Exact-title and parameter searches through 2026 found no later resolution.

This is an original CC0 textbook restatement of a finite subproblem motivated by the cited MathOverflow thread and later thesis; no source prose was copied.

Discussion

Loading discussion.

Add a comment

Report comment

Flag this problem

Sign in to follow

Sign in in another tab, then return here.

Open sign-in in another tab

Report a problem

Report location:

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.