§2, p. 2 — Tutte–Berge/Gallai–Edmonds: a barrier with all components of odd and
ProvedTuranMatching.Clique.barrierextremal-graph-theorymatching-numberp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1turan-numbertutte-berge
Let be a graph on vertices with matching number . Then there is a set of vertices such that every connected component of has an odd number of vertices , and
This is the form of the Tutte–Berge / Gallai–Edmonds theorem used at the start of the proof of Theorem 1.1. It holds, for instance, for a maximal barrier, all of whose components are factor-critical.
Formalization Note The paper writes on the right-hand side, for an extremal graph whose matching number equals ; the statement here is the general theorem it cites, with in place of . The second relation of the page, , holds automatically because the components partition the vertices outside .
Preamble
import Mathlib import Definitions.Def_TuranMatching_Clique_Setting open Finset SimpleGraph
Formal statement
namespace TuranMatching.Clique
theorem barrier (n : ℕ) (G : SimpleGraph (Fin n)) :
∃ B : Finset (Fin n), IsOddBarrier G B (matchingNumber G) := by sorry
end TuranMatching.Clique
Source
Alon and Frankl, Turán graphs with bounded matching number, arXiv:2210.15076v1, p. 2, §2, second sentence (Tutte–Berge / Edmonds–Gallai, cf. Lovász–Plummer [2])
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.