isMatching_sup_disjoint_encard
For two matchings M and M' in G with disjoint vertex sets, their supremum M ⊔ M' is also a matching, and its edge cardinality is the sum of their edge cardinalities.
Statement
theorem isMatching_sup_disjoint_encard {V : Type*} {G : SimpleGraph V} (M M' : SimpleGraph.Subgraph G) (hM : M.IsMatching) (hM' : M'.IsMatching) (hd : Disjoint M.verts M'.verts) : (M ⊔ M').IsMatching ∧ (M ⊔ M').edgeSet.encard = M.edgeSet.encard + M'.edgeSet.encard
- Source
- step towards konig_matching_vertex_cover_num
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- konig_matching_vertex_cover_numKönig's theorem: in any finite bipartite simple graph G, the matching number is equal to the vertex cover number.
The proof, explained
The proof splits the theorem into two parts: showing that the supremum M ⊔ M' is a matching, and establishing the edge count equality. First, the supremum of two matchings is a matching whenever their supports are disjoint, which holds because the support of a matching equals its vertex set and the vertex sets are assumed disjoint. Second, the edge set of the supremum is the union of the edge sets, and this union is disjoint because any shared edge would have endpoints belonging to both matchings, contradicting the vertex disjointness assumption.
The supremum M ⊔ M' is a matching.
We split the conjunction into two goals. For the first conjunct, by general properties of matchings (`hM.sup hM'`), the supremum of two matchings is a matching provided their supports are disjoint. For any matching, the support equals its vertex set (`hM.support_eq_verts`), so the hypothesis `hd` that the vertex sets are disjoint implies their supports are disjoint, closing the first goal.
refine ⟨hM.sup hM' ?_, ?_⟩ · rwa [hM.support_eq_verts, hM'.support_eq_verts]
To show that the edge count of M ⊔ M' is the sum of their edge counts, it suffices to show that the edge sets of M and M' are disjoint.
The edge set of M ⊔ M' is the union of their edge sets by `SimpleGraph.Subgraph.edgeSet_sup`. By `Set.encard_union_eq`, the cardinality of the union of two sets is the sum of their cardinalities provided they are disjoint. Rewriting disjointness with `Set.disjoint_left` reduces the goal to showing that no edge belongs to both edge sets.
uses
SimpleGraph.Subgraph.edgeSet_sup,Set.encard_union_eq,Set.disjoint_left· rw [SimpleGraph.Subgraph.edgeSet_sup, Set.encard_union_eq] rw [Set.disjoint_left]
The edge sets of M and M' are disjoint, completing the proof.
We assume for contradiction that some edge e belongs to both M.edgeSet and M'.edgeSet. By `Sym2.ind`, the edge e is an unordered pair s(v, w). Since v is an endpoint of e (by `Sym2.mem_mk_left`), v must belong to the vertex set of M, and by the same reasoning v must belong to the vertex set of M'. Applying `Set.disjoint_left.mp` to the disjointness hypothesis `hd` of the vertex sets yields a contradiction.
uses
Sym2.ind,Sym2.mem_mk_left,Set.disjoint_left.mpintro e he he' induction e using Sym2.ind with | h v w => have hvM : v ∈ M.verts := M.mem_verts_of_mem_edge he (Sym2.mem_mk_left v w) have hvM' : v ∈ M'.verts := M'.mem_verts_of_mem_edge he' (Sym2.mem_mk_left v w) exact Set.disjoint_left.mp hd hvM hvM'
SimpleGraph.Subgraph.edgeSet_sup- The edge set of the supremum of two subgraphs is the union of their edge sets.
Set.encard_union_eq- If two sets are disjoint, the cardinality (encard) of their union is the sum of their cardinalities.
Set.disjoint_left- Two sets are disjoint if and only if no element in the first set belongs to the second set.
Sym2.ind- To prove a property for all unordered pairs in a symmetric square, it suffices to prove it for pairs of the form s(x, y).
Sym2.mem_mk_left- The vertex x is an element of the unordered pair s(x, y).
Set.disjoint_left.mp- If two sets are disjoint, then an element of the first set cannot be in the second set.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The supremum of two matchings with disjoint vertex sets is a matching whose edge count is the sum of their edge counts. -/theorem isMatching_sup_disjoint_encard {V : Type*} {G : SimpleGraph V} (M M' : SimpleGraph.Subgraph G) (hM : M.IsMatching) (hM' : M'.IsMatching) (hd : Disjoint M.verts M'.verts) : (M ⊔ M').IsMatching ∧ (M ⊔ M').edgeSet.encard = M.edgeSet.encard + M'.edgeSet.encard := by refine ⟨hM.sup hM' ?_, ?_⟩ · rwa [hM.support_eq_verts, hM'.support_eq_verts] · rw [SimpleGraph.Subgraph.edgeSet_sup, Set.encard_union_eq] rw [Set.disjoint_left] intro e he he' induction e using Sym2.ind with | h v w => have hvM : v ∈ M.verts := M.mem_verts_of_mem_edge he (Sym2.mem_mk_left v w) have hvM' : v ∈ M'.verts := M'.mem_verts_of_mem_edge he' (Sym2.mem_mk_left v w) exact Set.disjoint_left.mp hd hvM hvM'