General · EdgepediaOctober 10, 20267 min read

Kereszyély Corrádi

Kereszyély Corrádi is the spelling given in one wiki-mirror source for the Hungarian mathematician whose primary catalog records print his name as Corrádi Keresztély (Keresztély Corrádi), a combinatorialist and group theorist at Eötvös Loránd University whose name survives in mathematics through two distinct results: the Corrádi–Hajnal theorem on disjoint cycles in graphs (1963) and Corrádi's intersection lemma on the union of sets with bounded pairwise overlaps (1969).¹ His birth and death dates are not documented, and the biographical record is thin overall; the mathematics, by contrast, is well documented and still actively cited, and generalized.

Key fact	Detail
Name spelling	Primary Hungarian library catalog prints "Corrádi Keresztély"; the spelling "Kereszyély" appears only in a weak wiki-mirror source¹
Most cited work	"On the maximal number of independent circuits in a graph", with András Hajnal, Acta Math. Acad. Sci. Hungar. 14 (1963), 423–439; cited 329–332 times depending on the database record²^•³
Corrádi's lemma	If A₁,…,Aₙ are r-element sets with pairwise intersections of size at most k, their union has size at least r²n/(r+(n−1)k)⁴
Corrádi–Hajnal theorem	Every graph on n ≥ 3k vertices with minimum degree δ(G) ≥ 2k contains k disjoint cycles; the bound is sharp⁵

Life and career

Beyond the two named results, the record includes a 1964 note "A note on finite graphs" in Acta scientiarum mathematicarum volume 25, no. 1–2, pages 169–171, and a Hungarian-language group theory textbook, Csoportelmélet = Group Theory, published in 2010 and held in the Library of the Hungarian Academy of Sciences.¹

The documentary record is unusually thin for a mathematician with two named results: his birth and death dates, his nationality, and any formal doctoral students as distinct from co-authors are not documented in the public record. The strongest biographical anchors are bibliographic databases and Hungarian library catalogs, which print his name in Hungarian order as Corrádi Keresztély.¹

Corrádi's lemma: statement, origin, and proof idea

In the form given in Stasys Jukna's Extremal Combinatorics (Springer, 2011, Lemma 2.1): let A₁, A₂, …, Aₙ be r-element sets and X their union. If |Aᵢ ∩ Aⱼ| ≤ k for all i ≠ j, then

$|X| \geq \frac{r^{2} n}{r + (n-1)k}.$

It is now a standard tool, presented in Jukna's Extremal Combinatorics and in László Lovász's Combinatorial Problems and Exercises.⁴

The Corrádi–Hajnal theorem: the other result

In 1963, Corrádi and Hajnal proved a conjecture of Erdős: for all k ≥ 1 and n ≥ 3k, every graph G on n vertices with minimum degree δ(G) ≥ 2k contains k vertex-disjoint cycles, and the bound δ(G) ≥ 2k is sharp.⁵ The paper, "On the maximal number of independent circuits in a graph", appeared in Acta Mathematica Academiae Scientiarum Hungaricae 14 (1963), pages 423–439, DOI 10.1007/BF01895727, as cited by later peer-reviewed work.²^•⁶ (One bibliographic database record gives different pagination and DOI for the same title, and another metadata record misprints the authors as Gabriel Andrew Dirac and P. Erdős; the peer-reviewed citations to [CH63] Corrádi and Hajnal are the reliable attribution.³^•²)

The theorem sits in the minimum-degree packing family that the Hajnal–Szemerédi theorem extended to all complete graphs as clique factors.⁷ In the triangle case it reads: any n-vertex graph without k+1 vertex-disjoint triangles has δ(G) ≤ k + (n−k)/2.⁸

Uses and influence

Both results have generated substantial downstream work.

Refinements of the theorem. Enomoto and Wang proved an Ore-type version: for all k ≥ 1 and n ≥ 3k, every graph on n vertices contains k disjoint cycles provided that d(x) + d(y) ≥ 4k − 1 for all distinct nonadjacent vertices x, y.⁵ Kierstead, Kostochka, and Yeager (2016) characterized the graphs with δ(G) ≥ 2k − 1 containing k disjoint cycles, answering the simple-graph case of a 1963 question of Dirac, and gave a polynomial-time algorithm for fixed k.⁵ A 2017 paper resolved the hardest case n = 3k of the Ore-type strengthening, where additional exceptional graphs appear for k = 3 and existence of k disjoint cycles becomes equivalent to an equitable k-coloring of the complement.⁶

Density and random extensions. A density version of the theorem determines, for sufficiently large n, the maximum number of edges in an n-vertex graph without vertex-disjoint triangles, extending Moon's 1968 extension of Mantel's theorem; the exact answer involves four different extremal graph families in four regimes of k, and Moon's extremal graph E1(n, k) is extremal only when n ≥ 9k/2 + 3.²^•⁸ The theorem has also been extended to sparse random graphs: if p(n) ≥ (log n / n)^{1/2}, then asymptotically almost surely every subgraph of G(n, p) with minimum degree at least (2/3 + o(1))np contains a triangle packing covering all but at most O(p^{−2}) vertices, with the threshold optimal up to the (log n)^{1/2} factor.⁹ Directed analogs exist as well: Wang proved that every directed graph on 3k vertices with minimum total degree δ_t ≥ 3(3k−1)/2 has a directed C₃-factor, a bound that is tight.¹⁰

The lemma in practice. Corrádi's lemma remains a working tool in extremal combinatorics, cited through standard texts and formalized in Lean's mathlib4 library as Finset.corradi_mul_le, with the inequality stated in the polynomial form n²r² + n|X|k ≤ n|X|r + n²|X|k.⁴

Lemma versus theorem: clearing up the confusion

The two results carrying Corrádi's name are unrelated in content. Corrádi's lemma is a set-intersection counting bound about the union of n r-element sets with pairwise overlaps at most k; the Corrádi–Hajnal theorem is a minimum-degree condition forcing k vertex-disjoint cycles in a graph.⁴^•⁵ The theorem is a two-author result, co-authored with András Hajnal, and belongs to the Hajnal–Szemerédi packing family; the lemma is a single-author problem Corrádi posed for the 1968 Schweitzer competition.²^•⁷

By the numbers

The 1963 Corrádi–Hajnal paper is Corrádi's most cited work, with 332 citations in one author-profile record and 329 in the publication record, a small discrepancy between database snapshots.³ The contrast with his co-author is stark: Hajnal's record shows an h-index of 53 with 10,811 citations, against Corrádi's h-index of 5 with 432 citations in the publication record, so a single co-authored paper accounts for the large majority of Corrádi's recorded citations.³ Quantitatively, the lemma guarantees a union of size at least r²n/(r+(n−1)k), and the theorem guarantees k disjoint cycles once n ≥ 3k and δ(G) ≥ 2k.⁴^•⁵

Recent developments

Post-2023 activity concerns the mathematics, not the biography.

Formalization. Corrádi's lemma was formalized in Lean's mathlib4 library as Finset.corradi_mul_le, meaning the statement is now machine-verified and available for use in formalized proofs.⁴

Density generalizations. A February 2023 arXiv paper (published in the Canadian Journal of Mathematics in 2025) presents a general method, for nondegenerate r-graphs F and t in [0, c_F·n], for determining the maximum number of edges in an n-vertex r-graph avoiding t+1 vertex-disjoint copies of F, applying to edge-critical graphs, the Fano plane, generalized triangles, hypergraph expansions, expanded triangles, and hypergraph books, and framed as a step toward a general density version of the Corrádi–Hajnal theorem.¹¹^•⁷ A 2025 paper in the SIAM Journal on Discrete Mathematics determines the same extremal function for t up to ε_F·n, generalizing Hou et al. (JCTB 2025) and extending Gan et al. (2023), Bushaw–Kettle (2014), and Khormali–Palmer (2022), and yields a rainbow version applicable to anti-Ramsey numbers.¹²

References

Initially written Oct 10, 2026 · Edited: Oct 11, 2026; Oct 15, 2026; Oct 25, 2026