Id: palomar/PALOMAR-2026-11-12-000004 Url: https://github.com/jtraverso/lovasz-gf-factor/tree/87f7fef730446522d4f1eb27bc90d50b370e1574 Json: https://data.palomar-registry.org/entries/PALOMAR-2026-11-12-000004-v1.json Repo: https://github.com/jtraverso/lovasz-gf-factor Tags: math.CO, msc:05C70 Score: 0 Title: Lovász's (g,f)-factor theorem Trust: high Domain: math.CO Source: palomar Authors: Juan Pablo Traverso Gianini Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Verified: true Discussed: 0 Published: 2026-11-12 Formalized: true Formalizes: title=Subgraphs with prescribed valencies identifier=doi:10.1016/S0021-9800(70)80033-3 relationship=formalizes Formalizes: title=A simple existence criterion for (g < f)-factors identifier=doi:10.1016/0012-365X(90)90387-W relationship=formalizes Page: https://delphi.science/r/palomar/PALOMAR-2026-11-12-000004 A Lean 4 / Mathlib proof of Lovász's (g,f)-factor theorem (1970): for a finite simple graph G and g ≤ f : V → ℕ, G has a spanning subgraph H with g(v) ≤ deg_H(v) ≤ f(v) for every vertex if and only if, for all disjoint vertex sets S and T, h(S,T) ≤ Σ_{v∈S} f(v) + Σ_{v∈T} (deg_{G−S}(v) − g(v)), where h(S,T) is the number of components C of G − (S ∪ T) with g = f on C and Σ_{v∈C} f(v) + e(C,T) odd (lovasz_gf_factor). As a corollary, the criterion of Heinrich, Hell, Kirkpatrick and Liu for g < f, without the component term (gf_factor_of_lt). The proof reduces the theorem to Tutte's f-factor…