{"id":"palomar/PALOMAR-2026-11-12-000008","url":"https://github.com/jtraverso/erdos-wilson-class-one/tree/e24f896005a8678e16ac1c7ac943184fdda6d852","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-11-12-000008-v1.json","repo":"https://github.com/jtraverso/erdos-wilson-class-one","tags":["math.CO","msc:05C15","msc:05C80"],"score":0,"title":"Erdős–Wilson: almost every graph is of class one","trust":"high","domain":"math.CO","source":"palomar","authors":["Juan Pablo Traverso Gianini"],"reviews":0,"subject":"math.CO","summary":"A Lean 4 / Mathlib proof of the theorem of Erdős and Wilson (1977) that almost every graph is of class one: among the 2^C(n,2) labelled graphs on Fin n, the proportion whose line graph is Δ(G)-colourable tends to 1 (erdos_wilson). On the way it proves that almost every graph has a unique vertex of maximum degree (tendsto_unique_maxDegree) and that a graph with at most one vertex of maximum degree is of class one (colorable_of_subsingleton_maxDegree, the special case of Fournier's theorem imported from PALOMAR-2026-11-08-000009). The probabilistic part is a second-moment argument with…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"verified":true,"discussed":0,"published":"2026-11-12","reactions":{},"formalized":true,"formalizes":[{"title":"On the chromatic index of almost all graphs","identifier":"doi:10.1016/0095-8956(77)90039-9","relationship":"formalizes"}]}