A Short Proof and Generalization of the Rainbow Cycle Theorem and Improved Bounds for Binary Even-Query LCCs

A rainbow cycle in a list-edge-colored graph is a cycle where no color appears more than once. We give a short and simple proof of a result of [ABSZZ] showing that a properly edge-colored n-vertex graph with average degree Ω(log nloglog n) always contains a rainbow cycle, and generalize it to weighted graphs with edges list colored with list size at most and where the total weight of all edges containing a given color i incident to a vertex is at most $Δ$, showing that Ω₍Δlog nloglog n) average degree guarantees a rainbow cycle. Using the reduction of [AG26] and the new generalized rainbow cycle theorem, we prove that for r≥ 3, every binary linear r-query locally correctable code E:F₂ᵏ→ F₂ⁿ satisfies k≤ Õ(n1-2/(r-1)) by showing a rainbow analogue of the odd r-LDC lower bounds of [BHKL25,JM25], closing the gap between the best known lower bounds for odd- and even-query binary linear r-LCCs.