Graph theory · one-factorizations · rainbow spanning trees

Brualdi–Hollingsworth Conjecture

Collaboration beta

Can every one-factorization of a complete graph on 2m vertices, for m at least 3, be repartitioned into m spanning trees that each use every factor color exactly once?

E (K_{2 m}) = T_{1} ⊔ \dots ⊔ T_{m}, | T_{i} \cap F_{c} | = 1

Listed inDouglas West’s REGS open-problem collection

Known results and sources

Perfect-matchings supply the colors; the conjecture asks for a partition into rainbow spanning trees.

Research problem

Exact mathematical statement

Let

E(K_{2m})=F_0\sqcup\cdots\sqcup F_{2m-2}

be a one-factorization of $K_{2m}$ . For $m\ge 3$ , the conjecture asserts that there is a partition

E(K_{2m})=T_1\sqcup\cdots\sqcup T_m

where every $T_i$ is a spanning tree and

|T_i\cap F_c|=1 \qquad (1\le i\le m,\ 0\le c\le 2m-2).

The case $m=2$ is an exact exception and is not part of the conjecture.

Problem infographic

Problem at a glance

A scientific editorial plate explains the Brualdi–Hollingsworth conjecture as two simultaneous organizations of the edges of a complete graph. Perfect-matching rows F₀ through F₂ₘ₋₂ each contain m disjoint edges. One edge selected from every row forms a full color transversal with 2m−1 edges; when connected, it is a rainbow spanning tree. The open question asks whether all edges can always be partitioned into m such trees with exactly one edge of every factor in each tree. A compact K₄ boundary example shows a rainbow star beside its complementary rainbow triangle, explaining why the conjecture begins at m at least 3. — A one-factorization colors the edges of K₂ₘ with 2m−1 perfect matchings. The Brualdi–Hollingsworth conjecture asks whether, for m ≥ 3, those same edges can always be repartitioned into m spanning trees that each take exactly one edge from every factor. The excluded m = 2 case splits into a star and a triangle rather than two trees. The general conjecture remains open.

Current mathematical picture

Where work on Brualdi–Hollingsworth Conjecture stands

Partially resolved

The exact paired-root endpoint and the common-root auxiliary-graph route remain provisional approaches to the Brualdi-Hollingsworth conjecture. Revision 17 adds exact global perfect-matching installation and refactor reachability, a scoped nonlocked-cycle destruction lemma, and a rooted seed-tree criterion that can guarantee one tree factor. It also isolates the genuine missing steps: a global potential descent-or-lock theorem, elimination of locked Hall kernels, and existence of a suitable color-correct seed. No complete all-orders proof or counterexample is reported, and this page does not independently verify the current work's derivations.

Strongest supported footholdRevision-11 two-front calculus

The exact two-front budget yields local escape thresholds, eliminates the immediate eleven-to-five branch, and gives candidate four- and eleven-front top-only moves.

Evidence posture · Reported result

Leading routePaired-root augmented endpoint

The exact target remains an integral cross-perfect augmented-base allocation satisfying (PR1)–(PR4) for at least one permitted choice of preceding data.

Route status · Active route

Useful failurePersistent safety from endpoint separation

Revision 15 refutes the inference from one-step reserve-one safety to permanent safety after later reserve depletion.

Route status · Refuted route

Main reductionRevision-13 laminar-memory reduction

Separation/absorption and multi-front collision formulas reduce ordinary global descent to a history-compatible local-selection theorem.

Evidence posture · Reported reduction

Priority open bridgeProve repair-cascade termination

Construct a well-founded potential tracking laminar inclusion, exact reserves, zero-reserve locations, and strict absorption or jump progress so every permitted reserve-accounted repair cascade terminates.

Task status · Blocked by the current route

Research-record correctionResearch-record correction

We corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Reader-facing record corrected; mathematics unchanged

Work mapped so far

Brualdi–Hollingsworth Conjecture in numbers

8.1kretained lines of mathematical investigation8,097 in the current working snapshot

Argument development: 6,772 · 84%
Explored or eliminated routes: 264 · 3%
Computational analysis: 156 · 2%
Open obligations: 380 · 5%
Definitions and setup: 525 · 6%

28selected mapped statements15routes investigated11reported milestones10open questions6contribution-ready tasks

How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Proposed byRichard A. Brualdi, Susan HollingsworthProposed1996Status checkedAug 2, 2026

Source dateAug 2, 2026

Recommended next task

Eliminate globally locked Hall kernels

Rule out the one- or two-kernel Hall structures of a globally locked cycle using bridge interfaces, matching origin, and first-forest constraints.

Suggested move: Audit the inherited two-kernel theorem and treat mixed kernel sizes p-1, p, and p+1 before pure kernels.

What would count as progress

Every admissible mixed and pure kernel configuration is excluded or reduced.
The proof retains the deleted first-edge and orientation data.

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

28 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

Scroll horizontally to explore the route

Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Active routePaired-root augmented endpoint

The exact target remains an integral cross-perfect augmented-base allocation satisfying (PR1)–(PR4) for at least one permitted choice of preceding data.

Route status · Active route

Active routeStrong-neutrality history route

Seek a paired-root-valid clearing exchange with nonnegative rank effect at every memory and every coarsening required by the meet/join proof.

Route status · Active route

Active routeReserve-accounted cascade route

Permit controlled reserve consumption, but prove every zero-reserve memory, reactivation, and re-clearing belongs to a well-founded terminating cascade.

Route status · Active route

Active routeGlobal refactor descent

Install selected perfect matchings and refactor complete regular complements, seeking a global cycle potential or a locked Hall-kernel certificate.

Route status · Active route

Active routeRooted seed-first orientation

Choose a color-correct spanning tree first, verify the exact rooted inequalities, and obtain one certified tree factor before addressing simultaneous factorization.

Route status · Active route

Explored alternatives

Other routes

10 recorded

Narrowed routeOrdinary high-spoke overload descent

This is the strongest supporting route and contains substantial conditional local progress, but it cannot be identified with paired-root completion.

Route status · Narrowed route

Narrowed routeDirect Stage-X large-successor branch

Revision 9 narrows the first large-successor geometry to all-singleton form above explicit quadratic thresholds; global descent and the low ranges remain open.

Route status · Narrowed route

Narrowed routeTwelve-block transfer branch

The inherited eleven-singleton normal form and seventeen-unit budget support local escape from p≥107 and top-only propagation, conditional on the audited chain.

Route status · Narrowed route

Browse 7 more explored routes

Narrowed routeTwenty-one-front transfer kernel

At p≥447 the route supplies a local clear pair, a small central-coarsening kernel, and a large successor gap; finite ranges, memory history, and paired-root validity remain open.

Route status · Narrowed route

Narrowed routeBounded four/eleven corridor

The recorded two-step theorem conditionally eliminates repeated 4↔11 cycling from p≥226, but every trajectory using weakened memory hypotheses must pass the Revision-15 re-audit.

Route status · Narrowed route

Refuted routePersistent safety from endpoint separation

Revision 15 refutes the inference from one-step reserve-one safety to permanent safety after later reserve depletion.

Route status · Refuted route

Useful but insufficientMaximal-memory endpoint dispersion

The Revision-14 concentration formula survives only as a one-step special case when every relevant memory has reserve at least one and no selected endpoint lies in a zero-reserve memory.

Route status · Useful but insufficient

Narrowed routeReserve-one dangerous-rectangle screen

Occupied 2×2 rectangles remain useful for frozen reserve-one support, but the method is invalid as a complete zero-reserve screen.

Route status · Narrowed route

Narrowed routeImmediate re-clearing thresholds

The six arithmetic thresholds survive under the exact two-front hypotheses; they do not close an arbitrary history or supply paired-root validity.

Route status · Narrowed route

Not yet justifiedSingle fixed-state negative search

A failed fixed allocation can reject that allocation only; the route is not justified as a BH counterexample without exhausting every load-bearing existential choice.

Route status · Not yet justified

Route statements and reductions

Statements the next route can inspect and build on

Route statementPaired-root augmented-base endpoint

After a permitted choice of root, reserved color, cross-perfect orientation, Rado-selected first forest, and deficient allocation, the current work reduces the target to an integral partition satisfying (PR1)–(PR4); the existential choice of the preceding data remains load-bearing.

Source-reported route statement

Route statementSeparation or strict absorption

Under strict coarsening clearance, full neutrality at an old front and every required coarsening, and finest-new-maximizer selection, the next remembered front is disjoint from the old one or strictly contains it.

Source-reported route statement · dependencies incomplete

Route statementLaminar-memory global descent reduction

If every defect-one singleton front has a strictly coarsening-clearing, history-compatible, top-only local selection, then remembered fronts become laminar and overload one cannot transfer forever, implying eventual ordinary overload descent.

Source-reported route statement · dependencies incomplete

Route statementExact memory-reserve update

For current reserve ω_A=−Δ(Π(A)) and a same-color transposition with t_A selected opposite endpoints in A, the exact local bound is g_τ(Π(A))≥−t_A, hence ω'A=ωA+g_τ(Π(A))≥ω_A−t_A.

Source-reported route statement

Route statementSlack-aware reserve-admissible pair count

After excluding selected endpoints in zero-reserve memories and pairs internal to inclusion-maximal reserve-one memories, the current work gives an exact admissible-pair count; if it exceeds the ordinary blocking-cell budget, one move preserves nonpositivity at every memory.

Source-reported route statement

Route statementScoped immediate re-clearing thresholds

For p≥510, every direct distinct-size reactivation among {4,11,21} satisfying all exact two-front hypotheses has an ordinary immediate re-clearing move neutral at the current source.

Source-reported route statement · dependencies incomplete

Route statementPaired-clear-pair or paired rotation

In every active-front state needed by the ordinary candidate chain, find a same-color transposition or coordinated rotation that preserves every owner forest, gives the required ordinary rank ascent, passes every paired-root deletion-cut test, controls all memory reserves, and belongs to a terminating global process.

Source-reported route statement · dependencies incomplete

Route statementPerfect-matching installation

Any perfect matching Q in a p-regular bipartite auxiliary graph can be made one factor of a one-factorization by factorizing the (p-1)-regular complement.

Source-reported route statement · dependencies incomplete

Route statementGlobal refactor reachability

Any ordered one-factorization can be transformed into any other by at most p-1 target-factor installation moves while retaining already installed target factors.

Source-reported route statement · dependencies incomplete

Route statementNonlocked-cycle destruction

If a directed cycle is not globally locked, one global matching installation can split its auxiliary edges across factors so that this exact directed cycle disappears.

Source-reported route statement · dependencies incomplete

Route statementRooted seed-tree orientation criterion

A spanning tree oriented away from the isolated root extends to the common-root orientation exactly when the nonroot degree and co-pair incidence inequalities hold; equivalently, the saturated nonroot vertices form a clique in F union T.

Source-reported route statement · dependencies incomplete

Route statementA color-correct seed gives one tree factor

A color-correct spanning tree satisfying the rooted criterion produces a common-root orientation with one installable tree perfect matching and a nonzero individual tree polynomial.

Source-reported route statement · dependencies incomplete

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

10 featured tasks

Eliminate globally locked Hall kernels

Rule out the one- or two-kernel Hall structures of a globally locked cycle using bridge interfaces, matching origin, and first-forest constraints.

Suggested move: Audit the inherited two-kernel theorem and treat mixed kernel sizes p-1, p, and p+1 before pure kernels.

Ready to work on

Attach paired-root deletion-cut signatures

For every selected heavy edge, record the two components left by deleting the outgoing edge from its owner tree and identify all candidate incoming edges that cross the cut.

Suggested move: Extend each candidate-pair certificate with both owner deletion cuts and the fixed-reserved-edge tree state.

Ready to work on

Find a rooted color-correct seed tree

For some permitted high-spoke state, root, and omitted color, construct a color-correct spanning tree satisfying the nonroot degree and saturated-clique criterion.

Suggested move: Use color-preserving basis exchanges while varying the omitted color, root, and first forest.

Ready to work on

Characterize zero-reserve one-unit loss

Give an exact ownerwise characterization of when a same-color exchange causes g_τ(Π(A))=−1 at a zero-reserve singleton memory.

Suggested move: Compute the quotient-rank effect for every candidate exchange at every zero-reserve memory instead of applying the reserve-one rectangle shortcut.

Ready to work on

Resolve the remaining parameter and large-front ranges

Handle p<107, the finite s=21 ranges, the 4→21 direction for 447≤p≤509 after reserve variables are installed, and the global large-front descent beyond the displayed local reductions.

Suggested move: Separate finite realizability searches from the all-orders memory theorem and preserve complete one-factorization certificates for any negative search result.

Ready to work on

Compute the actual s=21 admissible-pair count

For the twenty-heavy-cell s=21 state, compute N_adm from the live laminar memory tree and exact reserves rather than total remembered size.

Suggested move: Record zero-reserve endpoints and inclusion-maximal reserve-one blocks, then apply the exact count formula to the selected heavy set.

Ready to work on

Prove repair-cascade termination

Suggested move: Test a lexicographic potential on the retained 4↔11 and s=21 transitions, recording exact rank effects at every memory after each move.

Blocked by the current route

Prove a simultaneously valid pair bound

Prove a Hall-type lower bound leaving a pair that is ordinary-clear, reserve-admissible, outside every relevant reserve-one dangerous rectangle, and paired-root valid for both owners.

Suggested move: After exact reserve and paired-cut signatures are available, count the pairs surviving all four filters simultaneously rather than separately.

Blocked by the current route

Prove global-refactor descent or lock

Find a well-founded potential such that every cyclic one-factorization admits a strictly decreasing global refactor or contains a genuinely globally locked directed cycle.

Suggested move: Analyze a potential-minimal factorization under every perfect-matching installation, beginning with directed triangles.

Work already reported in progress

Audit the inherited candidate chain

Recheck the load-bearing Revision-8 and post-Revision-8 identities in the mandatory order, then incorporate the Revision-15 reserve correction into every retained trajectory before extending the route.

Suggested move: Stop at the first failed item in the combined mandatory audit; do not use later candidate consequences until their dependencies survive.

Work already reported in progress

Sourced mathematical context

The known mathematical landscape

Context collected Aug 2, 2026

Current statusPartially resolved

The conjecture is proved for every sufficiently large order, in the stronger form that all trees in the decomposition can be isomorphic. The cited theorem does not settle the original all-orders statement for every even complete graph K_n with n>4.

[3][5]

External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

2021
Peer reviewedGlock, Kühn, Montgomery, and Osthus proved exact decompositions for all sufficiently large orders, with all rainbow spanning trees isomorphic.[3]
2019
Peer reviewedMontgomery, Pokrovskiy, and Sudakov proved an asymptotic version, producing (1−o(1))n/2 edge-disjoint rainbow spanning trees.[4]
2018
PreprintA linear number Ω(n) of edge-disjoint rainbow spanning trees was proved for every properly edge-coloured complete graph.[1]
1996
Peer reviewedBrualdi and Hollingsworth proved that every one-factorization in the conjecture contains two edge-disjoint rainbow spanning trees.[2]

Mathematical neighborhood

Related results and reusable starting points

Current focusBrualdi–Hollingsworth conjecture

Related problemConstantine’s isomorphic rainbow spanning-tree conjecture

Constantine requires the decomposing rainbow trees to be pairwise isomorphic; the 2021 theorem settles both conjectures for sufficiently large order.

[3]

Solved special caseKaneko–Kano–Suzuki rainbow spanning-tree conjecture

Kaneko–Kano–Suzuki asks for floor(n/2) edge-disjoint rainbow spanning trees under an arbitrary proper edge-colouring, not only a one-factorization.

[5][3]

Related problemRota’s basis conjecture

Rainbow spanning-tree decomposition is a graphic-matroid analogue of decomposing arrays of matroid bases into transversal bases.

[3]

Later mathematical changes

What changed after the initial research map

Later recorded revisions that changed the mathematics, without inventing a date or an AI attribution.

Global refactors and a rooted seed criterion open two sharper routesRevision 17 proves source-reported global matching reachability and a rooted seed criterion, then isolates descent, locked-kernel elimination, and seed existence as the remaining bridges.

Changed the research frontierLater mathematical revision

Brualdi-Hollingsworth consolidated handoff revision 17 date · Dated Aug 2, 2026

The initial argument structure appears separately. Uploads, model runs, and presentation changes do not count as mathematical updates.

Research-record corrections

What changed in the research record

These notes describe corrections to cited passages, highlighted tasks, or connections between claims. The mathematical claims and their status did not change.

Research-record correctionWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

Research-record correctionWe corrected the cited passages. We removed a duplicate or outdated task or route step. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

The initial argument structure appears separately. Uploads, model runs, and presentation changes do not count as mathematical updates.

How the route was assembled

Argument structure

These stages follow the mathematical order of the supplied argument.

11 mapped milestonesretained argument map

Browse all 11 mapped stages

stage 1Exact all-orders target and exception
stage 2Paired-root augmented endpoint
stage 3Revision-8 branch foundation
stage 4Stronger direct Stage-X collapse
stage 5Twenty-one-front transfer kernel
stage 6General two-front calculus
stage 7Bounded four/eleven cycle conditionally excluded
stage 8Laminar-memory global descent reduction
stage 9Revision-14 one-step memory screens
stage 10Live memory reserve replaces persistent one-step safety
stage 11Paired-valid history theorem becomes the closing bridge

Exact all-orders target and exceptionThe current work fixes the exact rainbow spanning-tree decomposition target for m≥3 and excludes m=2.