{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"verified":true,"discussed":0,"published":"2026-11-12","reactions":{},"formalized":true,"formalizes":[{"title":"Subgraphs with prescribed valencies","identifier":"doi:10.1016/S0021-9800(70)80033-3","relationship":"formalizes"},{"title":"A simple existence criterion for (g < f)-factors","identifier":"doi:10.1016/0012-365X(90)90387-W","relationship":"formalizes"}]}