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