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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
preprint

The Erdős–Faber–Lovász Hypothesis Is Satisfiable

Christopher Mills
Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
preprint

The Erdős–Faber–Lovász Hypothesis Is Satisfiable

Christopher Mills
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

The Erdős–Faber–Lovász Hypothesis Is Satisfiable — Christopher Mills · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS