# P2894: Rainbow perfect matchings from eight spanning color classes

- ID: `P2894`
- Reference: `rainbow-perfect-matching-ten-vertices-eight-colors`
- Page: https://theoremdb.org/statements/P2894
- Record maturity: Reviewed problem with recorded work

## 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?

### Definitions

- **Definition.** 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.** 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.

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

## 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. 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](#reference-1)

## Work

### Evidence for the current status

**Claim 1 (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.

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.

A complete resolution must satisfy this condition: 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.

### Background and intake notes

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.

- Original intake status: 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.
- 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: Each color class contains at least five edges because it covers ten vertices. Equality forces that color class itself to be a perfect matching.

### Open directions

- **Route 1** (reported): 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](#reference-1)

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

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `rainbow-perfect-matching-ten-vertices-eight-colors`, 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. <a id="reference-1"></a>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. https://mathoverflow.net/questions/396913/a-rainbow-perfect-matching-in-an-edge-colored-graph-with-spanning-color-classes
   - 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
   - forum; reference source; checked 2026-07-31
   - Source use: citation_only
   - 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. <a id="reference-2"></a>Aaron Neugebauer, Rainbow Matchings in Color-Spanned Graphs, bachelor’s thesis, Julius-Maximilians-Universität Würzburg, July 4, 2022. Sections 5.4 and 6, bounds and open value k(10) https://www1.pub.informatik.uni-wuerzburg.de/pub/theses/2022-neugebauer-bachelorarbeit.pdf
   - website; reference source; checked 2026-07-31
   - Source use: citation_only
   - 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. <a id="reference-3"></a>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. Full proceedings article relevant to Rainbow perfect matchings from eight spanning color classes. https://doi.org/10.4230/LIPIcs.MFCS.2024.41
   - scholarly_publication; reference source; checked 2026-08-01
   - Source use: citation_only
   - 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.