simple_graph_eq_starGraph_of_forall_mem_edge
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
- simple_graph_is_tree_sum_choose_degree_eq_iff_starFor a tree T on k ≥ 2 vertices, σ₂(T) = C(k−1,2) if and only if T is a star K_{1,k−1}: some vertex r is adjacent to every other vertex and…
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.
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.
uses
SimpleGraph.starGraph_adjext a b rw [SimpleGraph.starGraph_adj] constructor
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).
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
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.
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' ▸ hIf 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.
uses
Ne.symmrcases 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
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 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