{"id":"palomar/PALOMAR-2026-11-08-000009","url":"https://github.com/jtraverso/fournier-class-one/tree/b7baf7b17023d2a2a6dd9650c0706fcabb3bc227","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-11-08-000009-v1.json","repo":"https://github.com/jtraverso/fournier-class-one","tags":["math.CO","msc:05C15"],"score":0,"title":"Fournier's theorem: graphs whose maximum-degree vertices induce a forest are 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 Fournier's theorem (1973): if the vertices of maximum degree of a finite simple graph G induce a forest, then G has a proper edge colouring with Δ(G) colours (fournier: G.lineGraph.Colorable G.maxDegree under (G.induce {v | G.degree v = G.maxDegree}).IsAcyclic). The proof takes an edge-minimal subgraph H of G that is not Δ(G)-edge-colourable; Vizing's theorem gives Δ(H) = Δ(G), and Vizing's adjacency lemma applied to every edge xy of H gives a neighbour of x of maximum degree other than y, so the maximum-degree vertices of H span a subgraph of minimum degree at…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"verified":true,"discussed":0,"published":"2026-11-08","reactions":{},"formalized":true,"formalizes":[{"title":"Colorations des arêtes d'un graphe","identifier":"","relationship":"formalizes"}]}