The Erdős–Faber–Lovász Hypothesis Is Satisfiable
The Erdős–Faber–Lovász conjecture states that $n$ cliques of size $n$, pairwise sharing at most one vertex, admit an $n$-colouring of their union. It was proved for all sufficiently large $n$ by Kang, Kelly, Kühn, Methuku, and Osthus in 2021 . We do not reprove it. Instead we settle the question a formal statement of it needs answered first and that the literature does not: whether the hypothesis –- $n$ cliques of size $n$ meeting pairwise in at most one point –- is ever actually realized, for every $n$, as opposed to being vacuous on some formalization of the setup. We give the explicit family that realizes it at every $n$, and prove it.
Authors
- Christopher Mills (ORCID: https://orcid.org/0000-0003-0003-0552)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-09-21
- DOI
- https://doi.org/10.5281/zenodo.22883465
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- preprint