matching_two_mul_encard_le_card
For any matching M in a finite graph G, twice its edge cardinality is at most the number of vertices.
Statement
theorem matching_two_mul_encard_le_card {V : Type*} [Fintype V] (G : SimpleGraph V) (M : G.Subgraph) (h : M.IsMatching) : 2 * M.edgeSet.encard ≤ (Fintype.card V : ℕ∞)
- Source
- step towards graph_matching_num_two_mul_le_card
- Verified
- 09 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The theorem is proved by constructing an injection f from Fin 2 × M.edgeSet into the vertex set V, which immediately yields the cardinality bound 2 * |M| ≤ |V|. The map f associates each pair (i, e) with the first endpoint of e if i = 0 and the second endpoint if i = 1. To prove injectivity, notice that each vertex in a matching belongs to at most one matching edge, so equal images force the edges to coincide. Furthermore, the two endpoints of an edge in a simple graph are adjacent and therefore distinct, preventing the two indices from differing on the same edge.
Any two distinct elements of Fin 2 are 0 and 1 in some order. automation
For a, b : Fin 2 with a ≠ b, finite case exhaustion using the decide tactic confirms that either a = 0 ∧ b = 1 or a = 1 ∧ b = 0.
revert a b decideThe representative endpoints of any edge in M are adjacent in M.
The edge e belongs to M.edgeSet by subtype definition. The quotient projection of Quot.out e.1 is e by Quot.out_eq, so rewriting by this identity shows that the first and second components of Quot.out e.1 are adjacent in M.
uses
Quot.out_eqhave he := e.2 have hq := Quot.out_eq e.1 rwa [← hq] at he
The vertex selected by f(M, p) belongs to the vertex set of M.
Unfolding f, if p.1 = 0, the function selects the first endpoint of p.2, which belongs to M.verts by the adjacency lemma matching_two_mul_encard_le_card_adj. If p.1 ≠ 0, it selects the second endpoint, which likewise belongs to M.verts.
uses
matching_two_mul_encard_le_card_adjdsimp [matching_two_mul_encard_le_card_f] split_ifs · exact (matching_two_mul_encard_le_card_adj M p.2).fst_mem · exact (matching_two_mul_encard_le_card_adj M p.2).snd_mem
When p.1 = 0, the unique matching edge incident to f(M, p) is p.2.
When p.1 = 0, f(M, p) is the first endpoint of p.2. Since M is a matching and the endpoints are adjacent by matching_two_mul_encard_le_card_adj, the unique incident edge in M is the unordered pair of these endpoints. Using Subtype.ext, congr_arg, and Subtype.val, together with Quot.out_eq, this edge is identified with p.2.
uses
matching_two_mul_encard_le_card_adj,Subtype.ext,congr_arg,Subtype.val,Quot.out_eqdsimp [matching_two_mul_encard_le_card_f] split_ifs with h0 · have hadj := matching_two_mul_encard_le_card_adj M p.2 have ht := h.toEdge_eq_of_adj hadj apply Subtype.ext have ht' : ((h.toEdge ⟨(Quot.out p.2.1).1, hadj.fst_mem⟩ : M.edgeSet) : Sym2 V) = s((Quot.out p.2.1).1, (Quot.out p.2.1).2) := congr_arg Subtype.val ht exact ht'.trans (Quot.out_eq p.2.1)
When p.1 ≠ 0, the unique matching edge incident to f(M, p) is also p.2.
When p.1 ≠ 0, f(M, p) is the second endpoint of p.2. By symmetry of adjacency, the second endpoint is adjacent to the first in M. The matching property assigns the incident edge as the unordered pair with endpoints reversed. Swapping them with Sym2.eq_swap and applying Quot.out_eq recovers p.2.
uses
matching_two_mul_encard_le_card_adj,Subtype.ext,congr_arg,Subtype.val,Sym2.eq_swap,Quot.out_eq· have hadj := matching_two_mul_encard_le_card_adj M p.2 have ht := h.toEdge_eq_of_adj hadj.symm apply Subtype.ext have ht' : ((h.toEdge ⟨(Quot.out p.2.1).2, hadj.snd_mem⟩ : M.edgeSet) : Sym2 V) = s((Quot.out p.2.1).2, (Quot.out p.2.1).1) := congr_arg Subtype.val ht have ht'' := ht'.trans Sym2.eq_swap exact ht''.trans (Quot.out_eq p.2.1)
If f(M, p1) = f(M, p2), then their edge components are equal: p1.2 = p2.2.
Equality of the mapped vertices f(M, p1) = f(M, p2) implies equality as elements of M.verts via Subtype.ext. Applying h.toEdge using congr_arg and simplifying each side with matching_two_mul_encard_le_card_toEdge proves p1.2 = p2.2.
uses
Subtype.ext,congr_arg,matching_two_mul_encard_le_card_toEdgeintro p1 p2 hp have h_edge : p1.2 = p2.2 := by have h_v : (⟨matching_two_mul_encard_le_card_f M p1, matching_two_mul_encard_le_card_mem M p1⟩ : M.verts) = ⟨matching_two_mul_encard_le_card_f M p2, matching_two_mul_encard_le_card_mem M p2⟩ := Subtype.ext hp have h_to := congr_arg h.toEdge h_v rw [matching_two_mul_encard_le_card_toEdge h p1, matching_two_mul_encard_le_card_toEdge h p2] at h_to exact h_to
If f(M, p1) = f(M, p2), then their index components are equal (p1.1 = p2.1), so p1 = p2.
Assuming for contradiction that p1.1 ≠ p2.1, lemma matching_two_mul_encard_le_card_fin2_cases gives two cases: (0, 1) or (1, 0). Simplifying f using if_pos and if_neg and using p1.2 = p2.2 forces the two endpoints of p2.2 to be equal. But adjacent vertices in a simple graph cannot be equal (matching_two_mul_encard_le_card_adj), yielding a contradiction. Thus p1.1 = p2.1, and Prod.ext concludes p1 = p2.
uses
matching_two_mul_encard_le_card_fin2_cases,if_pos,if_neg,matching_two_mul_encard_le_card_adj,Prod.exthave h_fin : p1.1 = p2.1 := by by_contra hne have hcases := matching_two_mul_encard_le_card_fin2_cases p1.1 p2.1 hne rcases hcases with ⟨h1, h2⟩ | ⟨h1, h2⟩ · dsimp [matching_two_mul_encard_le_card_f] at hp rw [h1, h2] at hp rw [if_pos rfl, if_neg (by decide)] at hp rw [h_edge] at hp exact (matching_two_mul_encard_le_card_adj M p2.2).ne hp · dsimp [matching_two_mul_encard_le_card_f] at hp rw [h1, h2] at hp rw [if_neg (by decide), if_pos rfl] at hp rw [h_edge] at hp have hadj := matching_two_mul_encard_le_card_adj M p2.2 exact hadj.symm.ne hp exact Prod.ext h_fin h_edge
Twice the edge cardinality of M is at most the vertex cardinality of V: 2 * |M.edgeSet| ≤ |V|.
By matching_two_mul_encard_le_card_injective, f is injective, so ENat.card_le_card_of_injective bounds the cardinality of Fin 2 × M.edgeSet by that of V. Applying ENat.card_prod and ENat.card_coe_set_eq evaluates the product cardinality as 2 * M.edgeSet.encard. Finally, ENat.card_eq_coe_fintype_card rewrites the bound as the cardinality of V, completing the proof.
uses
matching_two_mul_encard_le_card_injective,ENat.card_le_card_of_injective,ENat.card_prod,ENat.card_coe_set_eq,ENat.card_eq_coe_fintype_cardhave hinj := matching_two_mul_encard_le_card_injective h have hcard := ENat.card_le_card_of_injective hinj have hprod : ENat.card (Fin 2 × M.edgeSet) = 2 * M.edgeSet.encard := by rw [ENat.card_prod, ENat.card_coe_set_eq] simp rw [ENat.card_eq_coe_fintype_card (α := V)] at hcard exact hprod ▸ hcard
matching_two_mul_encard_le_card_fin2_cases- Any two distinct elements of {0, 1} are either 0 and 1 or 1 and 0.
Quot.out_eq- Projecting the canonical representative Quot.out q back to the quotient yields the original quotient element q.
matching_two_mul_encard_le_card_adj- The two representative endpoints chosen by Quot.out for any edge of subgraph M are adjacent in M.
Subtype.ext- Two elements of a subtype are equal if their underlying values are equal.
congr_arg- Applying a function to equal inputs produces equal outputs.
Subtype.val- The projection extracting the underlying value from a subtype element.
Sym2.eq_swap- An unordered pair is symmetric with respect to swapping its elements: s(a, b) = s(b, a).
matching_two_mul_encard_le_card_toEdge- For any matching M and pair p = (i, e), the unique edge of M incident to the vertex f(M, p) is e.
if_pos- If a condition c is true, then (if c then t else e) evaluates to t.
if_neg- If a condition c is false, then (if c then t else e) evaluates to e.
Prod.ext- Two ordered pairs are equal if their first components and second components are respectively equal.
matching_two_mul_encard_le_card_injective- For any matching M, the map f from Fin 2 × M.edgeSet to V is injective.
ENat.card_le_card_of_injective- An injective map between types implies that the cardinality of the domain is at most that of the codomain.
ENat.card_prod- The cardinality of a product type is the product of the cardinalities of its factor types.
ENat.card_coe_set_eq- The cardinality of a set coerced to a type equals its extended natural cardinality encard.
ENat.card_eq_coe_fintype_card- For a finite type, its cardinality as an extended natural number equals its cardinality as a natural number.
- Edges in SimpleGraph are represented as unordered pairs via the quotient type Sym2 V. Manipulating the endpoints of an edge requires extracting an ordered representative with Quot.out and transporting equalities across the quotient using Quot.out_eq and Sym2.eq_swap.
- Cardinality is computed in ℕ∞ (ENat, extended natural numbers) using encard, where the product cardinality formula ENat.card_prod holds before coercing to the finite cardinal Fintype.card V.
- The case exhaustion on Fin 2 in the first lemma is proved automatically by the decide tactic.
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.
open Sym2lemma matching_two_mul_encard_le_card_fin2_cases (a b : Fin 2) (h : a ≠ b) : (a = 0 ∧ b = 1) ∨ (a = 1 ∧ b = 0) := by revert a b decidenoncomputable def matching_two_mul_encard_le_card_f {V : Type*} {G : SimpleGraph V} (M : G.Subgraph) (p : Fin 2 × M.edgeSet) : V := if p.1 = 0 then (Quot.out p.2.1).1 else (Quot.out p.2.1).2lemma matching_two_mul_encard_le_card_adj {V : Type*} {G : SimpleGraph V} (M : G.Subgraph) (e : M.edgeSet) : M.Adj (Quot.out e.1).1 (Quot.out e.1).2 := by have he := e.2 have hq := Quot.out_eq e.1 rwa [← hq] at helemma matching_two_mul_encard_le_card_mem {V : Type*} {G : SimpleGraph V} (M : G.Subgraph) (p : Fin 2 × M.edgeSet) : matching_two_mul_encard_le_card_f M p ∈ M.verts := by dsimp [matching_two_mul_encard_le_card_f] split_ifs · exact (matching_two_mul_encard_le_card_adj M p.2).fst_mem · exact (matching_two_mul_encard_le_card_adj M p.2).snd_memlemma matching_two_mul_encard_le_card_toEdge {V : Type*} {G : SimpleGraph V} {M : G.Subgraph} (h : M.IsMatching) (p : Fin 2 × M.edgeSet) : h.toEdge ⟨matching_two_mul_encard_le_card_f M p, matching_two_mul_encard_le_card_mem M p⟩ = p.2 := by dsimp [matching_two_mul_encard_le_card_f] split_ifs with h0 · have hadj := matching_two_mul_encard_le_card_adj M p.2 have ht := h.toEdge_eq_of_adj hadj apply Subtype.ext have ht' : ((h.toEdge ⟨(Quot.out p.2.1).1, hadj.fst_mem⟩ : M.edgeSet) : Sym2 V) = s((Quot.out p.2.1).1, (Quot.out p.2.1).2) := congr_arg Subtype.val ht exact ht'.trans (Quot.out_eq p.2.1) · have hadj := matching_two_mul_encard_le_card_adj M p.2 have ht := h.toEdge_eq_of_adj hadj.symm apply Subtype.ext have ht' : ((h.toEdge ⟨(Quot.out p.2.1).2, hadj.snd_mem⟩ : M.edgeSet) : Sym2 V) = s((Quot.out p.2.1).2, (Quot.out p.2.1).1) := congr_arg Subtype.val ht have ht'' := ht'.trans Sym2.eq_swap exact ht''.trans (Quot.out_eq p.2.1)theorem matching_two_mul_encard_le_card_injective {V : Type*} {G : SimpleGraph V} {M : G.Subgraph} (h : M.IsMatching) : Function.Injective (matching_two_mul_encard_le_card_f M) := by intro p1 p2 hp have h_edge : p1.2 = p2.2 := by have h_v : (⟨matching_two_mul_encard_le_card_f M p1, matching_two_mul_encard_le_card_mem M p1⟩ : M.verts) = ⟨matching_two_mul_encard_le_card_f M p2, matching_two_mul_encard_le_card_mem M p2⟩ := Subtype.ext hp have h_to := congr_arg h.toEdge h_v rw [matching_two_mul_encard_le_card_toEdge h p1, matching_two_mul_encard_le_card_toEdge h p2] at h_to exact h_to have h_fin : p1.1 = p2.1 := by by_contra hne have hcases := matching_two_mul_encard_le_card_fin2_cases p1.1 p2.1 hne rcases hcases with ⟨h1, h2⟩ | ⟨h1, h2⟩ · dsimp [matching_two_mul_encard_le_card_f] at hp rw [h1, h2] at hp rw [if_pos rfl, if_neg (by decide)] at hp rw [h_edge] at hp exact (matching_two_mul_encard_le_card_adj M p2.2).ne hp · dsimp [matching_two_mul_encard_le_card_f] at hp rw [h1, h2] at hp rw [if_neg (by decide), if_pos rfl] at hp rw [h_edge] at hp have hadj := matching_two_mul_encard_le_card_adj M p2.2 exact hadj.symm.ne hp exact Prod.ext h_fin h_edge/-- For any matching M in a finite graph G, twice its edge cardinality is at most the number of vertices. -/theorem matching_two_mul_encard_le_card {V : Type*} [Fintype V] (G : SimpleGraph V) (M : G.Subgraph) (h : M.IsMatching) : 2 * M.edgeSet.encard ≤ (Fintype.card V : ℕ∞) := by have hinj := matching_two_mul_encard_le_card_injective h have hcard := ENat.card_le_card_of_injective hinj have hprod : ENat.card (Fin 2 × M.edgeSet) = 2 * M.edgeSet.encard := by rw [ENat.card_prod, ENat.card_coe_set_eq] simp rw [ENat.card_eq_coe_fintype_card (α := V)] at hcard exact hprod ▸ hcard