Rainbow Cycles Reach The Half-Vertex Bound

Rainbow cycle problems ask how local colour multiplicity forces a globally colour-distinct cycle. The motivating target here is Aharoni’s strengthening of the Caccetta-Häggkvist conjecture: if an n-vertex graph has n edge colours and every colour appears at least r times, should it contain a rainbow cycle of length at most $\lceil n/r \rceil$? This paper resolves the first nontrivial case, $r=2$, and ties it back to the known $r=2$ case of Caccetta-Häggkvist for directed graphs.

Core Contribution

The main theorem is sharp: every simple n-vertex graph whose edges are coloured with n colours, each used at least twice, contains a rainbow cycle of length at most $\lceil n/2 \rceil$. The result is not just an existence proof for some short rainbow cycle; it gives the exact threshold for the natural extremal function when the number of colours equals the number of vertices.

The authors also show why this is the right bound. For a graph on vertex set $\mathbb{Z}/n\mathbb{Z}$ with edges $i(i+1)$ and $i(i+2)$, colouring both edges by i, the shortest rainbow cycle has length $\lceil n/2 \rceil$. Figure 1 gives the seven-vertex instance, where the shortest rainbow cycle has length 4.

Technical Approach

The proof starts with a useful reduction. A weaker “properly coloured cycle” version of Aharoni’s conjecture would imply Caccetta-Häggkvist: orient each directed arc into an undirected edge and colour it by its tail. A properly edge-coloured cycle then corresponds to a directed cycle, because any failure would force two incident edges of the cycle to have the same colour.

For the main theorem, the authors assume a smallest counterexample. Minimality lets them take every colour class to have exactly two edges. They first prove that some vertex has all incident edges of distinct colours. Otherwise, at every vertex there are two same-coloured incident edges; orienting such pairs away from the vertex and applying the known Caccetta-Häggkvist theorem for minimum outdegree 2 would produce a directed cycle of length at most $\lceil n/2 \rceil$, which translates back into a rainbow cycle.

Results and Analysis

The graph result is a theorem, not an experiment: the quantitative content is the exact upper bound $\lceil n/2 \rceil$ and the matching construction showing equality. The paper goes further by defining the rainbow girth function $f(n,t)$ for n-vertex graphs with $2t$ edges and all colour classes of size 2. It determines the full range $t \leq n$: $f(n,t)=\infty$ for $t\leq n-2$, $f(n,t)=n-1$ for $t=n-1$, and $f(n,t)=\lceil n/2 \rceil$ for $t=n$. This makes the threshold behaviour unusually explicit: dropping from n colours to n-1 colours changes the forced rainbow girth from half the vertices to almost all vertices, and dropping to n-2 colours removes any guarantee of a rainbow cycle.

For $t>n$, the authors use a theorem of Bollobás and Szemerédi on graph girth to obtain

for $n\geq4$ and $k\geq2$. This is an upper bound rather than an exact formula, and the authors explicitly leave improvement of this range as an open problem.

Matroid Extension

The matroid section is more mixed. The natural analogue asks whether a simple rank-$(n-1)$ matroid with n colours, each class of size at least 2, must contain a rainbow circuit of size at most $\lceil n/2 \rceil$. The theorem holds for graphic matroids as a direct consequence of the graph result, and the authors prove it for cographic matroids by translating rainbow cocircuits through a graph decomposition and degree-counting argument.

But the general matroid statement fails. The authors construct an infinite family of binary matroids for even $n\geq6$: simple rank-$(n-1)$ binary matroids on $2n$ elements, coloured into n pairs, in which every rainbow circuit has size strictly greater than $n/2$. The evidence therefore supports a precise conclusion: the graph theorem is sharp, the cographic extension is valid, and binary matroids are too broad a setting for the same bound.