Lemma 8.2.5 — the incidence matrix of a bipartite graph is totally unimodular
ProvedMatousekLP.Integrality.incidenceMatrix_totallyUnimodularbipartite-graphgraph-theoryp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1total-unimodularity
Let be a finite bipartite graph and let be its vertex–edge incidence matrix, with if and otherwise. Then
that is, every square submatrix of has determinant , or .
Together with Lemma 8.2.4 this shows that the matching and vertex-cover integer programs of a bipartite graph have the same optima as their LP relaxations, which is the link between total unimodularity and König's theorem.
Formalization Note Rows are indexed by the vertex type and columns by the edge set of ; bipartiteness is the existence of some bipartition IsBipartite G.
Preamble
import Mathlib import Definitions.Def_MatousekLP_Integrality_BipartiteGraph import Definitions.Def_MatousekLP_Integrality_IncidenceMatrix
Formal statement
namespace MatousekLP.Integrality
theorem incidenceMatrix_totallyUnimodular {V : Type*} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (hG : IsBipartite G) :
(incidenceMatrix G).IsTotallyUnimodular := by sorry
end MatousekLP.Integrality
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 146, Lemma 8.2.5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.