AFTD Auto-Formalizing Theoretical Domains

simple_graph_eq_starGraph_of_forall_mem_edge

theoremverified

A connected graph in which every edge contains the vertex r is the star centred at r.

Statement

theorem simple_graph_eq_starGraph_of_forall_mem_edge {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) (hconn : G.Connected) (r : V)
    (hr : ∀ e ∈ G.edgeSet, r ∈ e) : G = SimpleGraph.starGraph r
Source
Helper for arXiv:2610.12109 (Sharp linear Turán remainders for cycle and edge extremality), Lemma 2.5 (equality case of the upper bound: the extremal tree is a star).
Verified
12 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

To prove that G is the star graph centered at r, we show that two vertices a, b are adjacent in G if and only if they are distinct and at least one of them is r. For the forward direction, any edge connects distinct vertices and must contain r by hypothesis, so one of its endpoints is r. For the reverse direction, connectedness implies that every vertex c ≠ r has a walk to r; the first edge along this walk contains r, forcing it to connect c directly to r. Thus any vertex distinct from r is adjacent to r, which completes the characterization.

  1. The graph equality G = SimpleGraph.starGraph r reduces to showing that a and b are adjacent in G if and only if a ≠ b and (a = r ∨ b = r).

    By graph extensionality (ext a b), two simple graphs are equal if and only if they have the same adjacency relation. By SimpleGraph.starGraph_adj, two vertices are adjacent in the star graph centered at r precisely when they are distinct and at least one of them is r. Splitting with constructor divides the proof into the two directions of this equivalence.

    lines 4–6

    uses SimpleGraph.starGraph_adj

      ext a b
      rw [SimpleGraph.starGraph_adj]
      constructor
  2. Any two adjacent vertices in G are distinct and at least one is r.

    Assume a and b are adjacent in G. Because simple graphs contain no self-loops, a ≠ b. Furthermore, the undirected edge s(a, b) belongs to the edge set of G, so by the hypothesis that every edge contains r, we have r ∈ s(a, b). By Sym2.mem_iff, this means r = a or r = b. Symmetrizing these equalities yields a = r (via Or.inl) or b = r (via Or.inr).

    lines 7–13

    uses Sym2.mem_iff, Or.inl, Or.inr

      · intro h
        refine ⟨G.ne_of_adj h, ?_⟩
        have := hr s(a, b) h
        rw [Sym2.mem_iff] at this
        rcases this with h' | h'
        · exact Or.inl h'.symm
        · exact Or.inr h'.symm
  3. Every vertex c ≠ r is adjacent to r in G.

    To prove the reverse implication, we unpack the assumption that a ≠ b and a = r ∨ b = r, and first establish a key lemma: every vertex c distinct from r is adjacent to r in G. Since G is connected, there is a walk from c to r. The walk cannot be empty (nil) because that would mean c = r, contradicting c ≠ r. Hence the walk starts with an edge from c to some vertex d. By hypothesis, the edge s(c, d) contains r, so by Sym2.mem_iff, either r = c or r = d. Since c ≠ r, we must have d = r, meaning the edge connects c directly to r.

    lines 14–26

    uses Sym2.mem_iff

      · rintro ⟨hab, hab'⟩
        -- the endpoint different from r has a neighbour, which must be r
        have key : ∀ c, c ≠ r → G.Adj c r := by
          intro c hc
          obtain ⟨p⟩ := hconn.preconnected c r
          cases p with
          | nil => exact absurd rfl hc
          | @cons _ d _ h _ =>
            have := hr s(c, d) h
            rw [Sym2.mem_iff] at this
            rcases this with h' | h'
            · exact absurd h'.symm hc
            · exact h' ▸ h
  4. If a ≠ b and at least one of a or b is r, then a and b are adjacent in G.

    We case-split on whether a = r or b = r. If a = r, then b ≠ r by Ne.symm applied to a ≠ b, so the key lemma shows that b is adjacent to r = a; by symmetry of adjacency, a and b are adjacent. If b = r, then a ≠ r since a ≠ b, so the key lemma directly shows that a is adjacent to r = b.

    lines 27–29

    uses Ne.symm

        rcases hab' with rfl | rfl
        · exact (key b (Ne.symm hab)).symm
        · exact key a hab
SimpleGraph.starGraph_adj
In a star graph centered at r, vertices x and y are adjacent if and only if x ≠ y and (x = r or y = r).
Sym2.mem_iff
An element a belongs to the unordered pair s(b, c) if and only if a = b or a = c.
Or.inl
If A holds, then the disjunction A ∨ B holds.
Or.inr
If B holds, then the disjunction A ∨ B holds.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.

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_eq_starGraph_of_forall_mem_edge {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) (hconn : G.Connected) (r : V)    (hr : ∀ e ∈ G.edgeSet, r ∈ e) : G = SimpleGraph.starGraph r := by  ext a b  rw [SimpleGraph.starGraph_adj]  constructor  · intro h    refine ⟨G.ne_of_adj h, ?_⟩    have := hr s(a, b) h    rw [Sym2.mem_iff] at this    rcases this with h' | h'    · exact Or.inl h'.symm    · exact Or.inr h'.symm  · rintro ⟨hab, hab'⟩    -- the endpoint different from r has a neighbour, which must be r    have key : ∀ c, c ≠ r → G.Adj c r := by      intro c hc      obtain ⟨p⟩ := hconn.preconnected c r      cases p with      | nil => exact absurd rfl hc      | @cons _ d _ h _ =>        have := hr s(c, d) h        rw [Sym2.mem_iff] at this        rcases this with h' | h'        · exact absurd h'.symm hc        · exact h' ▸ h    rcases hab' with rfl | rfl    · exact (key b (Ne.symm hab)).symm    · exact key a hab
See it in the graphDiscuss this resultChallenge it