Chetwynd–Hilton 1989: regular graphs of degree at least ½(√7 − 1)|V| are 1-factorizable
Source: github.com/jtraverso/chetwynd-hilton-1989/tree/0f6e485529e8…
A Lean 4 / Mathlib proof of Theorem 2 of Chetwynd and Hilton, "1-factorizing regular graphs of high degree — an improved bound" (Discrete Math. 75 (1989)): a d-regular simple graph of even order with d ≥ ½(√7 − 1)|V| (≈ 0.823|V|) is d-edge-colourable (CH89.lineGraph_colorable_of_isRegular_sqrt7), with the integer form |V| = 2n, 7n² ≤ (d + n)² (CH89.lineGraph_colorable_of_isRegular_nat). The article's proof of Theorem 1 contains an unjustified step ("we may moreover suppose that x_j comes before w_j in the list (r_m, …, r_t, l_1, …, l_m)"), which fails for an arbitrary maximal matching M₀;…
Comments and reviews
No comments yet.
API
curl /api/v1/records/palomar/PALOMAR-2026-11-12-000006
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-12-000006/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-12-000006/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'