Rigidity of the deficit-one rainbow-cycle obstruction

Definitions and mathematical statement

The source fragment says that on $|V|=d$ vertices a condition $\sum_i\delta_{G_i}(v)\geq d$ for every vertex forces a rainbow cycle, and says replacing $d$ vertices by $d+1$ makes the assertion false. Its notation and preceding hypotheses are missing. The supplied verification identifies this as the second half of Seymour's Conjecture6.5 in Blair Sullivan's summary of the2006 AIM workshop, with a prefix in neighboring source code AIM-COMBINATORICS-0167 referring to the hypotheses of Conjecture6.1. The following heading6.1.3 is an extraction artifact, not an extra hypothesis. Since the referenced hypotheses are not supplied here, the full conjecture is not silently reconstructed from the degree sum alone.

The aid studies a precise list-labelled directed-graph interpretation. Let an underlying functional digraph on $n\geq2$ vertices be loopless, with exactly one outgoing arc per vertex. Each arc $e$ carries a finite nonempty list $L(e)$ of available labels. A directed cycle is rainbow when its arcs admit pairwise distinct representatives from their lists. The labelled outdegree load is $\lambda(v)=|L(e_v)|$ in this functional case; equivalently, it is the sum of outdegrees in the label subgraphs when each arc is present in every listed label.

The reported deficit-one classification is \[ \lambda(v)\geq n-1\quad\text{for every }v \] and no rainbow directed cycle if and only if the underlying digraph is a spanning directed $n$-cycle and every arc list is the same set of exactly $n-1$ labels. Thus neither extra trees nor a shorter cycle can occur in a functional obstruction at this load. The converse uses the fact that a directed $n$-cycle needs $n$ different labels. The statement is restricted to functional digraphs, not an assertion about every list-labelled digraph.

For each $d\geq1$, take the directed $(d+1)$-cycle and place the common palette $[d]=\{1,\ldots,d\}$ on every arc. Every vertex has labelled outdegree $d$ but the only directed cycle is not rainbow. This verifies the source's sharpness example under the stated list interpretation. Adding one fresh label to any single arc creates a rainbow cycle. The classification says that, up to relabeling, this is the unique functional deficit-one obstruction, not the unique possible obstruction in the broader unresolved conjecture.

The aid's result therefore resolves a restricted rigidity and repair question while leaving the complete Seymour conjecture, including its missing inherited hypotheses, outside the supplied theorem.

Short English statement

The source is a truncated conjecture with missing earlier hypotheses. The aid rigorously classifies its functional-digraph boundary case: a nonrainbow obstruction must be one spanning cycle with a common palette one label too small. This both gives the stated sharpness example and explains why one new label repairs it.

Sources

• Local UnsolvedMath registry, permanent ID $20001043$, source code catalogue entry, supplied fragment, verification note and research summary; canonical local record aim-combinatorics-notes.json, notes[167].
• Blair Sullivan's summary of the2006 AIM workshop The Caccetta--Haggkvist conjecture, page6, Seymour's Conjecture6.5 as identified in the supplied verification; URL https://aimath.org/WWN/caccetta/caccetta.pdf. The extract/source-item label6.1 is retained as a cross-reference ambiguity. No PDF was retrieved.
• The verification refers to neighboring source code AIM-COMBINATORICS-0167 for the missing prefix, which itself points to Conjecture6.1 hypotheses. No full authoritative bibliographic citation for the auxiliary list-digraph classification is supplied; the original literature field is empty.
• Research attempt1: partial result; problem open at the recorded run, registry status partially solved; supplied rigor label "proved", novelty confidence "low". The machine-generated aid is not peer reviewed and requires independent verification before citation.