Lovász's (g,f)-factor theorem
Source: github.com/jtraverso/lovasz-gf-factor/tree/87f7fef730446522…
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/palomar/PALOMAR-2026-11-12-000004
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-12-000004/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-000004/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'