{
 "id": "ep6cjd0n7c",
 "slug": "kereszyely-corradi",
 "title": "Kereszyély Corrádi",
 "updated": "2026-10-25",
 "topic_path": [
  {
   "id": "physical",
   "label": "Physical world and mathematics",
   "api_url": "https://www.edgepedia.org/api/v1/topics/physical"
  },
  {
   "id": "physical.scientists",
   "label": "Physical and mathematical scientists",
   "api_url": "https://www.edgepedia.org/api/v1/topics/physical.scientists"
  },
  {
   "id": "physical.scientists.mathematics-statistics",
   "label": "Mathematicians and statisticians",
   "api_url": "https://www.edgepedia.org/api/v1/topics/physical.scientists.mathematics-statistics"
  },
  {
   "id": "physical.scientists.mathematics-statistics.logicians-set-theorists-and-combinatoria",
   "label": "Logicians, set theorists, and combinatorialists",
   "api_url": "https://www.edgepedia.org/api/v1/topics/physical.scientists.mathematics-statistics.logicians-set-theorists-and-combinatoria"
  },
  {
   "id": "physical.scientists.mathematics-statistics.logicians-set-theorists-and-combinatoria.graph-theorists",
   "label": "Graph theorists",
   "api_url": "https://www.edgepedia.org/api/v1/topics/physical.scientists.mathematics-statistics.logicians-set-theorists-and-combinatoria.graph-theorists"
  }
 ],
 "geo": [
  {
   "id": "geo.eeu.t1946.physical.scientists.mathematics-statistics.logicians-set-theorists-and-combinatoria",
   "label": "Eastern Europe · 1946 to 2000: Logicians, set theorists, and combinatorialists",
   "api_url": "https://www.edgepedia.org/api/v1/geo/geo.eeu.t1946.physical.scientists.mathematics-statistics.logicians-set-theorists-and-combinatoria",
   "path": [
    {
     "id": "geo.eeu",
     "label": "Eastern Europe",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.eeu"
    },
    {
     "id": "geo.eeu.t1946",
     "label": "Eastern Europe · 1946 to 2000",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.eeu.t1946"
    },
    {
     "id": "geo.eeu.t1946.physical",
     "label": "Physical world and mathematics",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.eeu.t1946.physical"
    },
    {
     "id": "geo.eeu.t1946.physical.scientists",
     "label": "Physical and mathematical scientists",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.eeu.t1946.physical.scientists"
    },
    {
     "id": "geo.eeu.t1946.physical.scientists.mathematics-statistics",
     "label": "Mathematicians and statisticians",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.eeu.t1946.physical.scientists.mathematics-statistics"
    },
    {
     "id": "geo.eeu.t1946.physical.scientists.mathematics-statistics.logicians-set-theorists-and-combinatoria",
     "label": "Logicians, set theorists, and combinatorialists",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.eeu.t1946.physical.scientists.mathematics-statistics.logicians-set-theorists-and-combinatoria"
    }
   ]
  }
 ],
 "excerpt": "Kereszyély Corrádi, also known as Corrádi Keresztély, is a Hungarian mathematician at Eötvös Loránd University known for the 1963 Corrádi–Hajnal theorem on disjoint cycles in graphs.",
 "snippet": "Kereszyély Corrádi, also known as Corrádi Keresztély, is a Hungarian mathematician at Eötvös Loránd University known for the 1963 Corrádi–Hajnal theorem on disjoint cycles in graphs.",
 "node": "physical.scientists.mathematics-statistics.logicians-set-theorists-and-combinatoria.graph-theorists",
 "markdown": "# Kereszyély Corrádi\n\n**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](https://www.edgepedia.org/eotvos-lorand-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).<sup>[1](https://www.contentas.ek.szte.hu/Record/acta14027/Details)</sup> 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.\n\n| Key fact | Detail |\n|---|---|\n| Name spelling | Primary Hungarian library catalog prints \"Corrádi Keresztély\"; the spelling \"Kereszyély\" appears only in a weak wiki-mirror source<sup>[1](https://www.contentas.ek.szte.hu/Record/acta14027/Details)</sup> |\n| 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<sup>[2](https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/density-corradihajnal-theorem/D0472298688A0106DDE8A674B4F43BDD)</sup><sup> • </sup><sup>[3](https://doi.org/10.1007/bf01895727)</sup> |\n| 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)<sup>[4](https://github.com/leanprover-community/mathlib4/pull/39936)</sup> |\n| Corrádi–Hajnal theorem | Every graph on n ≥ 3k vertices with minimum degree δ(G) ≥ 2k contains k disjoint cycles; the bound is sharp<sup>[5](https://arxiv.org/abs/1601.03791)</sup> |\n\n## Life and career\n\nBeyond 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](https://www.edgepedia.org/hungarian-academy-of-sciences).<sup>[1](https://www.contentas.ek.szte.hu/Record/acta14027/Details)</sup>\n\nThe 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.<sup>[1](https://www.contentas.ek.szte.hu/Record/acta14027/Details)</sup>\n\n## Corrádi's lemma: statement, origin, and proof idea\n\nIn 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\n\n\\[ |X| \\geq \\frac{r^{2} n}{r + (n-1)k}. \\]\n\nIt is now a standard tool, presented in Jukna's *Extremal Combinatorics* and in [László Lovász](https://www.edgepedia.org/laszlo-lovasz)'s *Combinatorial Problems and Exercises*.<sup>[4](https://github.com/leanprover-community/mathlib4/pull/39936)</sup>\n\n## The Corrádi–Hajnal theorem: the other result\n\nIn 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.<sup>[5](https://arxiv.org/abs/1601.03791)</sup> 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.<sup>[2](https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/density-corradihajnal-theorem/D0472298688A0106DDE8A674B4F43BDD)</sup><sup> • </sup><sup>[6](https://kostochk.web.illinois.edu/docs/2017/Abhandlungen17.pdf)</sup> (One bibliographic database record gives different pagination and DOI for the same title, and another metadata record misprints the authors as [Gabriel Andrew Dirac](https://www.edgepedia.org/gabriel-andrew-dirac) and P. Erdős; the peer-reviewed citations to [CH63] Corrádi and Hajnal are the reliable attribution.<sup>[3](https://doi.org/10.1007/bf01895727)</sup><sup> • </sup><sup>[2](https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/density-corradihajnal-theorem/D0472298688A0106DDE8A674B4F43BDD)</sup>)\n\nThe theorem sits in the minimum-degree packing family that the Hajnal–Szemerédi theorem extended to all complete graphs as clique factors.<sup>[7](https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/step-towards-a-general-density-corradihajnal-theorem/450F76F25E4FC5CC79413B3F2F496AE0)</sup> In the triangle case it reads: any n-vertex graph without k+1 vertex-disjoint triangles has δ(G) ≤ k + (n−k)/2.<sup>[8](https://researchonline.lse.ac.uk/id/eprint/67185/1/Allen_Density%20theorem_2016.pdf)</sup>\n\n## Uses and influence\n\nBoth results have generated substantial downstream work.\n\n**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.<sup>[5](https://arxiv.org/abs/1601.03791)</sup> 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.<sup>[5](https://arxiv.org/abs/1601.03791)</sup> 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.<sup>[6](https://kostochk.web.illinois.edu/docs/2017/Abhandlungen17.pdf)</sup>\n\n**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.<sup>[2](https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/density-corradihajnal-theorem/D0472298688A0106DDE8A674B4F43BDD)</sup><sup> • </sup><sup>[8](https://researchonline.lse.ac.uk/id/eprint/67185/1/Allen_Density%20theorem_2016.pdf)</sup> 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.<sup>[9](http://www.math.tau.ac.il/~samotij/papers/TrianglePacking-edited.pdf)</sup> 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.<sup>[10](https://ar5iv.labs.arxiv.org/html/1309.4520)</sup>\n\n**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.<sup>[4](https://github.com/leanprover-community/mathlib4/pull/39936)</sup>\n\n## Lemma versus theorem: clearing up the confusion\n\nThe 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.<sup>[4](https://github.com/leanprover-community/mathlib4/pull/39936)</sup><sup> • </sup><sup>[5](https://arxiv.org/abs/1601.03791)</sup> The theorem is a two-author result, co-authored with [András Hajnal](https://www.edgepedia.org/andras-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.<sup>[2](https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/density-corradihajnal-theorem/D0472298688A0106DDE8A674B4F43BDD)</sup><sup> • </sup><sup>[7](https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/step-towards-a-general-density-corradihajnal-theorem/450F76F25E4FC5CC79413B3F2F496AE0)</sup>\n\n## By the numbers\n\nThe 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.<sup>[3](https://doi.org/10.1007/bf01895727)</sup> 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.<sup>[3](https://doi.org/10.1007/bf01895727)</sup> 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.<sup>[4](https://github.com/leanprover-community/mathlib4/pull/39936)</sup><sup> • </sup><sup>[5](https://arxiv.org/abs/1601.03791)</sup>\n\n## Recent developments\n\nPost-2023 activity concerns the mathematics, not the biography.\n\n**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.<sup>[4](https://github.com/leanprover-community/mathlib4/pull/39936)</sup>\n\n**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](https://www.edgepedia.org/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.<sup>[11](https://arxiv.org/abs/2302.09849)</sup><sup> • </sup><sup>[7](https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/step-towards-a-general-density-corradihajnal-theorem/450F76F25E4FC5CC79413B3F2F496AE0)</sup> 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.<sup>[12](https://dl.acm.org/doi/10.1137/25M1782972)</sup>\n\n## References\n\n1. [Staff View: A note on finite graphs, SZTE repository record](https://www.contentas.ek.szte.hu/Record/acta14027/Details)\n2. [A Density Corrádi–Hajnal Theorem, Canadian Journal of Mathematics](https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/density-corradihajnal-theorem/D0472298688A0106DDE8A674B4F43BDD)\n3. [On the maximal number of independent circuits in a graph — publication record, Exa library](https://doi.org/10.1007/bf01895727)\n4. [Corrádi's intersection lemma, mathlib4 PR #39936](https://github.com/leanprover-community/mathlib4/pull/39936)\n5. [On the Corrádi–Hajnal Theorem and a question of Dirac, arXiv:1601.03791](https://arxiv.org/abs/1601.03791)\n6. [Sharpening an Ore-type version of the Corrádi–Hajnal theorem, Abh. Math. Semin. Univ. Hambg. (2017)](https://kostochk.web.illinois.edu/docs/2017/Abhandlungen17.pdf)\n7. [A step towards a general density Corrádi–Hajnal theorem, Canadian Journal of Mathematics (2025)](https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/step-towards-a-general-density-corradihajnal-theorem/450F76F25E4FC5CC79413B3F2F496AE0)\n8. [A density Corrádi–Hajnal Theorem, LSE Research Online eprint](https://researchonline.lse.ac.uk/id/eprint/67185/1/Allen_Density%20theorem_2016.pdf)\n9. [Corrádi and Hajnal's theorem for sparse random graphs](http://www.math.tau.ac.il/~samotij/papers/TrianglePacking-edited.pdf)\n10. [On directed versions of the Corrádi–Hajnal Corollary, arXiv:1309.4520](https://ar5iv.labs.arxiv.org/html/1309.4520)\n11. [A step towards a general density Corrádi–Hajnal Theorem, arXiv:2302.09849](https://arxiv.org/abs/2302.09849)\n12. [A Partial Edge-Density Version of the Corrádi–Hajnal Theorem in Hypergraphs, SIAM Journal on Discrete Mathematics (2025)](https://dl.acm.org/doi/10.1137/25M1782972)\n\n---\n*Topic: Encyclopedia › Physical world and mathematics › Physical and mathematical scientists › Mathematicians and statisticians › Logicians, set theorists, and combinatorialists › Graph theorists*\n\n*Initially written Oct 10, 2026 · Edited: Oct 11, 2026; Oct 15, 2026; Oct 25, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n",
 "same_as": [],
 "url": "https://www.edgepedia.org/kereszyely-corradi",
 "markdown_url": "https://www.edgepedia.org/kereszyely-corradi.md",
 "license": {
  "name": "Edgepedia Community License 1.0",
  "url": "https://www.edgepedia.org/edgepedia/license",
  "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.",
  "spdx": "LicenseRef-Edgepedia-Community-1.0"
 },
 "credit": "\"Kereszyély Corrádi\", Edgepedia (EdgeChat), https://www.edgepedia.org/kereszyely-corradi. Edgepedia Community License 1.0.",
 "credit_md": "\"[Kereszyély Corrádi](https://www.edgepedia.org/kereszyely-corradi)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/kereszyely-corradi](https://www.edgepedia.org/kereszyely-corradi). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).",
 "credit_html": "\"<a href=\"https://www.edgepedia.org/kereszyely-corradi\">Kereszyély Corrádi</a>\", Edgepedia (EdgeChat), <a href=\"https://www.edgepedia.org/kereszyely-corradi\">https://www.edgepedia.org/kereszyely-corradi</a>. <a href=\"https://www.edgepedia.org/edgepedia/license\">Edgepedia Community License 1.0</a>.",
 "speakable": "Kereszyély Corrádi, also known as Corrádi Keresztély, is a Hungarian mathematician at Eötvös Loránd University known for the 1963 Corrádi–Hajnal theorem on disjoint cycles in graphs."
}