AFTD Auto-Formalizing Theoretical Domains

isMatching_sup_disjoint_encard

theoremverified

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

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.

  1. 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.

    lines 5–6

      refine ⟨hM.sup hM' ?_, ?_⟩
      · rwa [hM.support_eq_verts, hM'.support_eq_verts]
  2. 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.

    lines 7–8

    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]
  3. 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.

    lines 9–14

    uses Sym2.ind, Sym2.mem_mk_left, Set.disjoint_left.mp

        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'
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

/-- 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'
See it in the graphDiscuss this resultChallenge it