AFTD Auto-Formalizing Theoretical Domains

multigraph_cubic_third_edge

theoremverified

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

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.

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

    line 5

    uses Set.ncard_eq_three.mp

      obtain ⟨x, y, z, hxy, hxz, hyz, hs⟩ := Set.ncard_eq_three.mp (hcubic v)
  2. 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.

    lines 6–8

    uses Set.ext_iff.mp

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

    lines 9–11

    uses Or.inl, Or.inr

      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))
  4. 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.

    lines 12–26

    uses absurd

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

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

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]))
See it in the graphDiscuss this resultChallenge it