mono — Mathlib

English

A dual subgraph construction via spanningCoe yields equivalence of IsPerfectMatching between the target and source graphs.

Русский

Двойственная конструкция через spanningCoe даёт эквивалентность IsPerfectMatching между целевым и исходным графами.

LaTeX

$$Iff (G'.toSubgraph M.spanningCoe h).IsPerfectMatching M.IsPerfectMatching$$

Lean4

theorem mono {G G' : SimpleGraph V} (h : G ≤ G') (hmf : G'.IsMatchingFree) : G.IsMatchingFree :=
  by
  intro x
  by_contra! hc
  apply hmf (x.map (SimpleGraph.Hom.ofLE h))
  refine ⟨hc.1.map_ofLE h, ?_⟩
  intro v
  simp only [Subgraph.map_verts, Hom.coe_ofLE, id_eq, Set.image_id']
  exact hc.2 v

Похожие утверждения