AFTD Auto-Formalizing Theoretical Domains

simple_graph_line_graph_edge_unique_common_root_vertex

theoremverified

Every edge of the line graph of a simple graph is contained in a unique star clique of the root graph: its two distinct root edges have a unique common endpoint.

Statement

theorem simple_graph_line_graph_edge_unique_common_root_vertex
    (n : ℕ) (H : SimpleGraph (Fin n)) (e : Sym2 H.edgeSet)
    (he : e ∈ H.lineGraph.edgeSet) :
    ∃! v : Fin n, ∀ f ∈ e, v ∈ f.val
Source
Star-clique edge partition for the line-graph cover route.
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

An edge of the line graph corresponds to a pair of distinct, adjacent edges a ≠ b of the root graph H, which intersect at some vertex v. This vertex v serves as the witness for existence. If any vertex w also belongs to both a and b with w ≠ v, then since simple graph edges have size 2, both a and b would equal the edge {w, v}. This would force a = b, contradicting that they are distinct, so the common endpoint is unique.

  1. The line graph edge e consists of two distinct edges a ≠ b of H that share an endpoint v.

    We work classically and express the unordered pair e as s(a, b) for two edges a, b of H. Because e belongs to the edge set of the line graph, a and b are adjacent in the line graph. By the characterization of line-graph adjacency, a and b are distinct edges of H that have a common vertex v (that is, v ∈ a and v ∈ b).

    lines 5–9

    uses Sym2.ind, SimpleGraph.mem_edgeSet, SimpleGraph.lineGraph_adj_iff_exists.mp

      classical
      induction e using Sym2.ind with
      | h a b =>
        have hadj : H.lineGraph.Adj a b := (SimpleGraph.mem_edgeSet _).mp he
        obtain ⟨hab, v, hva, hvb⟩ := SimpleGraph.lineGraph_adj_iff_exists.mp hadj
  2. The common endpoint v belongs to every edge in e.

    We propose v as the unique common vertex. If f is an edge in the pair s(a, b), then f must be either a or b. Since v was chosen to belong to both a and b, it belongs to f in either case.

    lines 10–13

    uses Sym2.mem_iff

        refine ⟨v, ?_, ?_⟩
        · intro f hf
          rw [Sym2.mem_iff] at hf
          rcases hf with rfl | rfl <;> assumption
  3. The common endpoint is unique: any vertex w belonging to every edge in e equals v.

    Suppose w is another vertex belonging to every edge in e, so w ∈ a and w ∈ b. For contradiction, assume w ≠ v. Since each simple graph edge consists of exactly two distinct endpoints, an edge containing both w and v must equal the unordered pair s(w, v). Hence both a and b equal s(w, v), which means a = b. This contradicts the fact that a and b are distinct edges, so we conclude w = v.

    lines 14–20

    uses Sym2.mem_and_mem_iff, Subtype.ext

        · intro w hw
          have hwa : w ∈ a.val := hw a (by simp)
          have hwb : w ∈ b.val := hw b (by simp)
          by_contra hne
          have E1 : a.val = s(w, v) := (Sym2.mem_and_mem_iff hne).mp ⟨hwa, hva⟩
          have E2 : b.val = s(w, v) := (Sym2.mem_and_mem_iff hne).mp ⟨hwb, hvb⟩
          exact hab (Subtype.ext (E1.trans E2.symm))
Sym2.ind
Every element of the symmetric square Sym2 α is an unordered pair s(x, y) for some x, y : α.
SimpleGraph.mem_edgeSet
An unordered pair s(v, w) is in the edge set of a simple graph if and only if v and w are adjacent.
SimpleGraph.lineGraph_adj_iff_exists.mp
If two edges are adjacent in the line graph, then they are distinct and share at least one endpoint in the underlying graph.
Sym2.mem_iff
An element belongs to the unordered pair s(b, c) if and only if it equals b or c.
Sym2.mem_and_mem_iff
For two distinct elements x ≠ y, both x and y belong to an unordered pair z if and only if z = s(x, y).
Subtype.ext
Two terms of a subtype are equal if and only if their underlying values are equal.

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 simple_graph_line_graph_edge_unique_common_root_vertex    (n : ℕ) (H : SimpleGraph (Fin n)) (e : Sym2 H.edgeSet)    (he : e ∈ H.lineGraph.edgeSet) :    ∃! v : Fin n, ∀ f ∈ e, v ∈ f.val := by  classical  induction e using Sym2.ind with  | h a b =>    have hadj : H.lineGraph.Adj a b := (SimpleGraph.mem_edgeSet _).mp he    obtain ⟨hab, v, hva, hvb⟩ := SimpleGraph.lineGraph_adj_iff_exists.mp hadj    refine ⟨v, ?_, ?_⟩    · intro f hf      rw [Sym2.mem_iff] at hf      rcases hf with rfl | rfl <;> assumption    · intro w hw      have hwa : w ∈ a.val := hw a (by simp)      have hwb : w ∈ b.val := hw b (by simp)      by_contra hne      have E1 : a.val = s(w, v) := (Sym2.mem_and_mem_iff hne).mp ⟨hwa, hva⟩      have E2 : b.val = s(w, v) := (Sym2.mem_and_mem_iff hne).mp ⟨hwb, hvb⟩      exact hab (Subtype.ext (E1.trans E2.symm))
See it in the graphDiscuss this resultChallenge it