Zulip Chat Archive
Stream: graph theory
Topic: Formalization auxiliary result of Edmonds-Gallai
Roman Dragnyev (Feb 28 2026 at 12:24):
Hello hello, i'm a masters student doing a research semester; as a part of it i've formalized an auxiliary result (Thm 2.2.3) of the edmonds-gallai theorem from diestels book.
The main results are:
lemma exists_isPerfectMatching_iff_card_eq (h₀ : G.IsMatchableToComponents S)
(h₁ : ∀ (C : (G.induce Sᶜ).ConnectedComponent), (G.induce Sᶜ).IsFactorCriticalArea C.supp) :
card S = card (G.induce Sᶜ).ConnectedComponent ↔ ∃ M : Subgraph G, M.IsPerfectMatching := ...
and
theorem aux (G : SimpleGraph V) : ∃ (S : Set V),
(G.IsMatchableToComponents S) ∧
(∀ (C : (G.induce Sᶜ).ConnectedComponent), (G.induce Sᶜ).IsFactorCriticalArea C.supp) := ...
where
def IsFactorCriticalArea (G : SimpleGraph V) (S : Set V) : Prop :=
S.Nonempty ∧ ∀ v ∈ S, ∃ M : G.Subgraph, M.IsMatching ∧ M.support = S \ {v}
def IsMatchableToComponents (S : Set V) : Prop :=
∃ (f : S → (G.induce Sᶜ).ConnectedComponent),
Function.Injective f ∧ (∀ s : S, ∃ y ∈ (f s), G.Adj ↑s ↑y)
My code can be found here "https://github.com/wetpant93/pfs/blob/master/Pfs/edmonds_gallai.lean". It is currently a bit raw - a short summary of my formalization can be found here "https://github.com/wetpant93/pfs/blob/master/Summary-Edmonds-Gallai.pdf"; Given a bit more polish, is there some intrest in this?
Last updated: Feb 28 2026 at 14:05 UTC