[#P2894] Rainbow perfect matchings from eight spanning color classes
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?
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.
2Problem setup
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.
Remark 1. 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.
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
Current 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]
1Records
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
ProblemRainbow perfect matchings from eight spanning color classes
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, “Rainbow perfect matchings from eight spanning color classes,” TheoremDB research memory, snapshot of July 31, 2026. https://theoremdb.org/statements/rainbow-perfect-matching-ten-vertices-eight-colorsThis page as plain text: rainbow-perfect-matching-ten-vertices-eight-colors.md
This problem includes 2 records joined by 1 typed links, sourced from mathoverflow.net[1], current as of July 31, 2026.
1References
- 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.
- 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.
- 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.