multigraph_cubic_third_edge
In a multigraph (ends : E → Sym2 V) where every vertex lies on exactly three edges, two distinct edges e ≠ f at v leave a third edge g at v, distinct from both, and every edge at v is e, f or g.
Statement
theorem multigraph_cubic_third_edge {V E : Type*} {ends : E → Sym2 V} (hcubic : ∀ v, Set.ncard {e | v ∈ ends e} = 3) {v : V} {e f : E} (he : v ∈ ends e) (hf : v ∈ ends f) (hef : e ≠ f) : ∃ g, v ∈ ends g ∧ g ≠ e ∧ g ≠ f ∧ ∀ k, v ∈ ends k → k = e ∨ k = f ∨ k = g
- Source
- helper for truncation_local_states_strong_coloring_iff (arXiv:2610.41950 Lemma 2.1, PR-677)
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- truncation_local_states_strong_coloring_iffLemma 2.1 of arXiv:2610.41950. Let G be a loopless cubic multigraph, given by ends : E → Sym2 V (no Fintype or Finite instance on V or E…
The proof, explained
Because every vertex has degree three, the set of edges incident to v consists of exactly three pairwise distinct edges {x, y, z}. Given two distinct incident edges e and f, they must correspond to two different elements of this three-element set. The remaining third element is selected as g; by construction, it is incident to v, distinct from both e and f, and exhausts all edges incident to v.
The set of edges incident to v consists of three pairwise distinct edges x, y, and z.
By assumption, every vertex has degree 3, so the set {e | v ∈ ends e} has cardinality 3. The lemma Set.ncard_eq_three.mp extracts three pairwise distinct edges x, y, z such that {e | v ∈ ends e} = {x, y, z}.
uses
Set.ncard_eq_three.mpobtain ⟨x, y, z, hxy, hxz, hyz, hs⟩ := Set.ncard_eq_three.mp (hcubic v)An edge k is incident to v if and only if k = x, k = y, or k = z.
Applying set extensionality (Set.ext_iff.mp) to the equality {e | v ∈ ends e} = {x, y, z} shows that k is incident to v if and only if k belongs to {x, y, z}, which simplifies to k = x ∨ k = y ∨ k = z.
uses
Set.ext_iff.mphave mem : ∀ k, v ∈ ends k ↔ k = x ∨ k = y ∨ k = z := fun k => by have := Set.ext_iff.mp hs k simpa using this
Each of x, y, and z is an edge incident to v.
Using the right-to-left direction of the equivalence, we substitute k = x, k = y, and k = z respectively, using reflexivity of equality and disjunction introductions (Or.inl, Or.inr) to conclude that v ∈ ends x, v ∈ ends y, and v ∈ ends z.
uses
Or.inl,Or.inrhave hx := (mem x).2 (Or.inl rfl) have hy := (mem y).2 (Or.inr (Or.inl rfl)) have hz := (mem z).2 (Or.inr (Or.inr rfl))
There exists an edge g incident to v, distinct from e and f, such that every edge incident to v is e, f, or g.
Since e and f are incident to v, each must equal x, y, or z, leading to 9 cases. The 3 cases where e = f contradict the hypothesis e ≠ f (hef) and are eliminated with absurd. In each of the remaining 6 cases, e and f are two distinct elements among {x, y, z}, so the third remaining element is chosen as the witness g. The distinctness of g from e and f follows from the distinctness of x, y, z, and completeness holds because any incident edge k ∈ {x, y, z} must be e, f, or g.
uses
absurdrcases (mem e).1 he with rfl | rfl | rfl <;> rcases (mem f).1 hf with rfl | rfl | rfl <;> first | exact absurd rfl hef | (refine ⟨_, hx, ?_, ?_, ?_⟩ <;> first | (intro h; subst h; contradiction) | (intro k hk; rcases (mem k).1 hk with h | h | h <;> simp [h])) | (refine ⟨_, hy, ?_, ?_, ?_⟩ <;> first | (intro h; subst h; contradiction) | (intro k hk; rcases (mem k).1 hk with h | h | h <;> simp [h])) | (refine ⟨_, hz, ?_, ?_, ?_⟩ <;> first | (intro h; subst h; contradiction) | (intro k hk; rcases (mem k).1 hk with h | h | h <;> simp [h]))
Set.ncard_eq_three.mp- If a set has cardinality 3, there exist three pairwise distinct elements x, y, z such that the set is equal to {x, y, z}.
Set.ext_iff.mp- Two sets are equal only if they contain the same elements: s = t implies x ∈ s ↔ x ∈ t for all x.
Or.inl- Infers the disjunction a ∨ b from a proof of the left disjunct a.
Or.inr- Infers the disjunction a ∨ b from a proof of the right disjunct b.
absurd- Principle of explosion: from a proposition and its negation, any conclusion follows (a → ¬a → b).
- The case analysis on the pairs (e, f) ∈ {x, y, z}² is handled uniformly in Lean using tactical branching (`<;>`, `first`): the three diagonal cases where e = f contradict e ≠ f and are dismissed immediately, while the six off-diagonal cases each pick the remaining element of {x, y, z} as g, discharging the distinctness and completeness goals by contradiction and simplification.
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.
theorem multigraph_cubic_third_edge {V E : Type*} {ends : E → Sym2 V} (hcubic : ∀ v, Set.ncard {e | v ∈ ends e} = 3) {v : V} {e f : E} (he : v ∈ ends e) (hf : v ∈ ends f) (hef : e ≠ f) : ∃ g, v ∈ ends g ∧ g ≠ e ∧ g ≠ f ∧ ∀ k, v ∈ ends k → k = e ∨ k = f ∨ k = g := by obtain ⟨x, y, z, hxy, hxz, hyz, hs⟩ := Set.ncard_eq_three.mp (hcubic v) have mem : ∀ k, v ∈ ends k ↔ k = x ∨ k = y ∨ k = z := fun k => by have := Set.ext_iff.mp hs k simpa using this have hx := (mem x).2 (Or.inl rfl) have hy := (mem y).2 (Or.inr (Or.inl rfl)) have hz := (mem z).2 (Or.inr (Or.inr rfl)) rcases (mem e).1 he with rfl | rfl | rfl <;> rcases (mem f).1 hf with rfl | rfl | rfl <;> first | exact absurd rfl hef | (refine ⟨_, hx, ?_, ?_, ?_⟩ <;> first | (intro h; subst h; contradiction) | (intro k hk; rcases (mem k).1 hk with h | h | h <;> simp [h])) | (refine ⟨_, hy, ?_, ?_, ?_⟩ <;> first | (intro h; subst h; contradiction) | (intro k hk; rcases (mem k).1 hk with h | h | h <;> simp [h])) | (refine ⟨_, hz, ?_, ?_, ?_⟩ <;> first | (intro h; subst h; contradiction) | (intro k hk; rcases (mem k).1 hk with h | h | h <;> simp [h]))