simple_graph_is_tree_sum_choose_degree_eq_iff_star
For 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 there are no other edges (T = starGraph r).
Statement
theorem simple_graph_is_tree_sum_choose_degree_eq_iff_star {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hT : G.IsTree) (hk : 2 ≤ Fintype.card V) : ∑ v, (G.degree v).choose 2 = (Fintype.card V - 1).choose 2 ↔ ∃ r : V, G = SimpleGraph.starGraph r
- Formalizes
- arXiv:2610.12109 (Sharp linear Turán remainders for cycle and edge extremality), Lemma 2.5, equality case of the upper bound. The star K_{1,k−1} on the vertex set of T is Mathlib's starGraph r.
- Verified
- 12 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- simple_graph_is_tree_card_sub_two_le_sum_choose_degree_le_chooseFor a tree T on k ≥ 2 vertices, σ₂(T) = ∑_v C(d_T(v),2) satisfies k − 2 ≤ σ₂(T) ≤ C(k−1,2).
- simple_graph_sum_choose_degree_two_le_choose_card_edgeFinsetIn any finite simple graph, the number of pairs of edges sharing a vertex, ∑_v C(d(v),2), is at most C(|E|,2): two distinct edges share at…
- simple_graph_eq_starGraph_of_forall_mem_edgeA connected graph in which every edge contains the vertex r is the star centred at r.
- Used by 1
- op223_tree_fin_four_iso_path_or_starEvery tree on four vertices is isomorphic either to the path graph on four vertices or to the star K_{1,3}.
The proof, explained
The theorem characterizes trees on k ≥ 2 vertices whose sum of choose(degree, 2) reaches the maximum choose(k-1, 2) as precisely the star graphs K_{1, k-1}. The reverse direction is a direct calculation: the center has degree k - 1 and all other k - 1 vertices have degree 1, so the sum is choose(k-1, 2) + 0 = choose(k-1, 2). For the forward direction, double-counting pairs of incident edges shows that the number of pairs of edges sharing a vertex equals choose(|E|, 2), the total number of pairs of edges; because simple graphs cannot have multiple edges, this forces every pair of edges in G to intersect. Finally, picking an edge xy, if not all edges share x or all share y, one obtains edges yz and xz, creating a 3-cycle xyz which contradicts the fact that trees are acyclic.
The tree G has |E| = |V| - 1 edges, and the theorem splits into the forward and reverse implications.
For any tree, the number of edges plus one equals the number of vertices (|E| + 1 = |V|). We then split the if-and-only-if statement into two implications.
classical have hE : G.edgeFinset.card + 1 = Fintype.card V := hT.card_edgeFinset constructor
Assuming ∑_v choose(deg(v), 2) = choose(|V|-1, 2), every two distinct edges of G share a vertex.
Consider the set S of pairs (v, {e₁, e₂}) where e₁, e₂ are distinct edges incident to v. The cardinality of S is ∑_v choose(deg(v), 2) = choose(|V|-1, 2) = choose(|E|, 2). The projection (v, {e₁, e₂}) ↦ {e₁, e₂} maps S into the set of 2-element subsets of edges. Because G is a simple graph, two distinct vertices cannot be incident to the same two edges (which would mean both edges connect the same pair of vertices), so this projection is injective. Since S and the set of 2-element edge subsets have the exact same finite cardinality choose(|E|, 2), the projection is a bijection. Consequently, every pair of distinct edges {e₁, e₂} lies in the image, meaning they share a common incident vertex.
uses
Finset.card_sigma,Finset.sum_congr,Finset.card_powersetCard,SimpleGraph.card_incidenceFinset_eq_degree,SimpleGraph.incidenceFinset_subset,Sym2.mem_and_mem_iff,Finset.card_image_of_injOn,Finset.eq_of_subset_of_card_le,Finset.card_pair,Finset.mem_powersetCard,SimpleGraph.mem_incidenceFinset· intro hsum -- every two distinct edges share a vertex have hmeet : ∀ e₁ ∈ G.edgeSet, ∀ e₂ ∈ G.edgeSet, e₁ ≠ e₂ → ∃ w, w ∈ e₁ ∧ w ∈ e₂ := by let S := Finset.univ.sigma (fun v => (G.incidenceFinset v).powersetCard 2) have hS : S.card = ∑ v, (G.degree v).choose 2 := by rw [Finset.card_sigma] refine Finset.sum_congr rfl fun v _ => ?_ rw [Finset.card_powersetCard, SimpleGraph.card_incidenceFinset_eq_degree] have hsub : S.image (fun p => p.2) ⊆ G.edgeFinset.powersetCard 2 := by intro t ht simp only [Finset.mem_image, S, Finset.mem_sigma, Finset.mem_univ, true_and, Finset.mem_powersetCard] at ht ⊢ obtain ⟨⟨v, t⟩, ⟨hts, htc⟩, rfl⟩ := ht exact ⟨hts.trans (SimpleGraph.incidenceFinset_subset G v), htc⟩ have hinj : Set.InjOn (fun p : (Σ _ : V, Finset (Sym2 V)) => p.2) S := by intro p hp q hq hpq simp only [Finset.coe_sigma, Set.mem_sigma_iff, Finset.mem_coe, Finset.mem_univ, true_and, Finset.mem_powersetCard, S] at hp hq obtain ⟨v, t⟩ := p obtain ⟨w, t'⟩ := q simp only at hpq hp hq subst hpq by_cases hvw : v = w · subst hvw; rfl · exfalso obtain ⟨e₁, e₂, hne, rfl⟩ := Finset.card_eq_two.1 hp.2 have h1v := hp.1 (Finset.mem_insert_self _ _) have h2v := hp.1 (Finset.mem_insert_of_mem (Finset.mem_singleton_self _)) have h1w := hq.1 (Finset.mem_insert_self _ _) have h2w := hq.1 (Finset.mem_insert_of_mem (Finset.mem_singleton_self _)) rw [SimpleGraph.mem_incidenceFinset] at h1v h2v h1w h2w apply hne have key : ∀ e ∈ G.incidenceSet v, e ∈ G.incidenceSet w → e = s(v, w) := by intro e hev hew exact (Sym2.mem_and_mem_iff hvw).1 ⟨hev.2, hew.2⟩ rw [key _ h1v h1w, key _ h2v h2w] have hcard : (S.image (fun p => p.2)).card = (G.edgeFinset.powersetCard 2).card := by rw [Finset.card_image_of_injOn hinj, hS, hsum, Finset.card_powersetCard] congr 1 omega have heq := Finset.eq_of_subset_of_card_le hsub hcard.ge intro e₁ he₁ e₂ he₂ hne have hmem : ({e₁, e₂} : Finset (Sym2 V)) ∈ G.edgeFinset.powersetCard 2 := by rw [Finset.mem_powersetCard] refine ⟨?_, Finset.card_pair hne⟩ intro e he simp only [Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl <;> simpa rw [← heq] at hmem simp only [Finset.mem_image, S, Finset.mem_sigma, Finset.mem_univ, true_and, Finset.mem_powersetCard] at hmem obtain ⟨⟨v, t⟩, ⟨hts, -⟩, rfl⟩ := hmem have h1 := hts (Finset.mem_insert_self _ _) have h2 := hts (Finset.mem_insert_of_mem (Finset.mem_singleton_self _)) rw [SimpleGraph.mem_incidenceFinset] at h1 h2 exact ⟨v, h1.2, h2.2⟩
G contains at least one edge, connecting some vertices x and y.
Since |V| ≥ 2, there exist two distinct vertices. Because G is a tree, it is preconnected, so there is a path connecting them; the first step of this path provides an edge between two adjacent vertices x and y.
uses
Fintype.exists_pair_of_one_lt_card-- an edge xy obtain ⟨x, y, hxy⟩ : ∃ x y, G.Adj x y := by obtain ⟨x, y, hne⟩ := Fintype.exists_pair_of_one_lt_card (by omega : 1 < Fintype.card V) obtain ⟨p⟩ := hT.1.preconnected x y cases p with | nil => exact absurd rfl hne | cons h _ => exact ⟨_, _, h⟩
Either G is a star graph centered at x or y, or there exist edges e₁ not containing x and e₂ not containing y.
If every edge contains x, then because G is connected it is a star graph centered at x. Otherwise, there is an edge e₁ not containing x. Similarly, if every edge contains y, G is a star centered at y; otherwise, there is an edge e₂ not containing y.
uses
simple_graph_eq_starGraph_of_forall_mem_edgeby_cases hx : ∀ e ∈ G.edgeSet, x ∈ e · exact ⟨x, simple_graph_eq_starGraph_of_forall_mem_edge G hT.1 x hx⟩ push Not at hx obtain ⟨e₁, he₁, hxe₁⟩ := hx by_cases hy : ∀ e ∈ G.edgeSet, y ∈ e · exact ⟨y, simple_graph_eq_starGraph_of_forall_mem_edge G hT.1 y hy⟩ push Not at hy obtain ⟨e₂, he₂, hye₂⟩ := hy
The edges e₁ and e₂ must be of the form e₁ = s(y, z) and e₂ = s(x, z) for a common vertex z.
Since any two edges meet, e₁ meets the edge s(x, y). But x ∉ e₁, so e₁ must contain y, meaning e₁ = s(y, z) for some vertex z. Symmetrically, e₂ meets s(x, y) but y ∉ e₂, so e₂ must contain x, meaning e₂ = s(x, z') for some vertex z'. Since e₁ ≠ e₂ (as x ∈ e₂ but x ∉ e₁), e₁ and e₂ must also share a vertex w. Because y ∉ e₂ and x ∉ e₁, the shared vertex cannot be x or y, forcing w = z = z'. Thus e₁ = s(y, z) and e₂ = s(x, z).
uses
Sym2.mem_mk_left,Sym2.mem_mk_right,Sym2.mem_iff-- e₁ = s(y, z), e₂ = s(x, z'), and z = z' have hxy' : s(x, y) ∈ G.edgeSet := hxy obtain ⟨w₁, hw₁a, hw₁b⟩ := hmeet _ hxy' _ he₁ (fun h => hxe₁ (h ▸ Sym2.mem_mk_left x y)) obtain ⟨w₂, hw₂a, hw₂b⟩ := hmeet _ hxy' _ he₂ (fun h => hye₂ (h ▸ Sym2.mem_mk_right x y)) rw [Sym2.mem_iff] at hw₁a hw₂a have hw₁ : w₁ = y := hw₁a.resolve_left (fun h => hxe₁ (h ▸ hw₁b)) have hw₂ : w₂ = x := hw₂a.resolve_right (fun h => hye₂ (h ▸ hw₂b)) subst hw₁ hw₂ obtain ⟨z, rfl⟩ := (Sym2.mem_iff_exists.1 hw₁b) obtain ⟨z', rfl⟩ := (Sym2.mem_iff_exists.1 hw₂b) have hyz : G.Adj w₁ z := he₁ have hxz' : G.Adj w₂ z' := he₂ have hne12 : s(w₁, z) ≠ s(w₂, z') := fun h => hxe₁ (by rw [h]; exact Sym2.mem_mk_left _ _) obtain ⟨w₃, hw₃a, hw₃b⟩ := hmeet _ he₁ _ he₂ hne12 have hzz : z = z' := by rcases Sym2.mem_iff.1 hw₃a with h | h · exact absurd (h ▸ hw₃b) hye₂ · rw [h] at hw₃b rcases Sym2.mem_iff.1 hw₃b with h' | h' · exact absurd (show w₂ ∈ s(w₁, z) by rw [h']; exact Sym2.mem_mk_right _ _) hxe₁ · exact h' subst hzz
The existence of the edges s(x, y), s(y, z), and s(x, z) contradicts the acyclicity of G.
Since G is a tree, it is acyclic, so every edge is a bridge. In particular, the edge s(x, z) is a bridge, so deleting it must disconnect x and z. However, in G with s(x, z) deleted, x is still connected to y via s(x, y), and y is connected to z via s(y, z), since neither of those edges equals s(x, z). This path x - y - z shows x and z remain connected, contradicting that s(x, z) is a bridge.
uses
SimpleGraph.isBridge_iff,SimpleGraph.deleteEdges_adj,Set.mem_singleton_iff-- triangle w₂ - w₁ - z contradicts acyclicity: s(w₂, z) is a bridge exfalso have hbr := (SimpleGraph.isAcyclic_iff_forall_adj_isBridge.1 hT.2) hxz' rw [SimpleGraph.isBridge_iff] at hbr apply hbr have h1 : (G.deleteEdges {s(w₂, z)}).Adj w₂ w₁ := by simp only [SimpleGraph.deleteEdges_adj, Set.mem_singleton_iff] refine ⟨hxy, fun h => ?_⟩ rcases Sym2.eq_iff.1 h with ⟨-, h'⟩ | ⟨h', h''⟩ · exact G.ne_of_adj hyz h' · exact G.ne_of_adj hxy h''.symm have h2 : (G.deleteEdges {s(w₂, z)}).Adj w₁ z := by simp only [SimpleGraph.deleteEdges_adj, Set.mem_singleton_iff] refine ⟨hyz, fun h => ?_⟩ rcases Sym2.eq_iff.1 h with ⟨h', -⟩ | ⟨h', -⟩ · exact G.ne_of_adj hxy h'.symm · exact G.ne_of_adj hyz h' exact h1.reachable.trans h2.reachable
Conversely, if G is a star graph centered at r, then ∑_v choose(deg(v), 2) = choose(|V|-1, 2).
In a star graph centered at r, the center vertex has degree |V| - 1, and every other vertex has degree 1. Separating the term for r from the sum, the center contributes choose(|V|-1, 2), while every other vertex contributes choose(1, 2) = 0. The sum is therefore choose(|V|-1, 2).
uses
SimpleGraph.degree_starGraph_center,SimpleGraph.degree_starGraph_of_ne_center,Finset.add_sum_erase,Finset.mem_univ,Finset.sum_eq_zero,Finset.ne_of_mem_erase· rintro ⟨r, rfl⟩ have hc : (SimpleGraph.starGraph r).degree r = Fintype.card V - 1 := by convert SimpleGraph.degree_starGraph_center (r := r) have ho : ∀ v, v ≠ r → (SimpleGraph.starGraph r).degree v = 1 := fun v hv => by convert SimpleGraph.degree_starGraph_of_ne_center hv rw [← Finset.add_sum_erase _ _ (Finset.mem_univ r), hc, Finset.sum_eq_zero fun v hv => by rw [ho v (Finset.ne_of_mem_erase hv)]; rfl] simp
Finset.add_sum_erase- For any element a in a finite set s, the sum of a function over s equals the value at a plus the sum over s with a removed.
Finset.card_image_of_injOn- The image of a finite set s under a function injective on s has the same cardinality as s.
Finset.card_pair- The cardinality of a pair {a, b} with a ≠ b is 2.
Finset.card_powersetCard- The number of size-n subsets of a finite set s is choose(|s|, n).
Finset.card_sigma- The cardinality of a disjoint sum (sigma) of finite sets is the sum of their cardinalities.
Finset.eq_of_subset_of_card_le- If a finite subset s of t has |t| ≤ |s|, then s = t.
Finset.mem_powersetCard- A subset t is in powersetCard n s if and only if t ⊆ s and |t| = n.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
Finset.ne_of_mem_erase- An element in s with a removed is not equal to a.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their terms agree everywhere on that set.
Finset.sum_eq_zero- If every term in a sum over a finite set is zero, the sum is zero.
Fintype.exists_pair_of_one_lt_card- A finite type with cardinality greater than 1 contains at least two distinct elements.
SimpleGraph.mem_incidenceFinset- An edge e is in the incidence finset of v if and only if it belongs to the incidence set of v (i.e. is an edge incident to v).
SimpleGraph.card_incidenceFinset_eq_degree- The number of incident edges to v is the degree of v.
SimpleGraph.incidenceFinset_subset- The incident edges at any vertex v form a subset of all edges of the graph.
SimpleGraph.isBridge_iff- An edge s(u, v) is a bridge if and only if deleting it leaves u and v disconnected.
SimpleGraph.deleteEdges_adj- Two vertices are adjacent in G with a set of edges deleted if and only if they are adjacent in G and the edge between them was not deleted.
SimpleGraph.degree_starGraph_center- In a star graph centered at r, the degree of r is the total number of vertices minus 1.
SimpleGraph.degree_starGraph_of_ne_center- In a star graph centered at r, every vertex other than r has degree 1.
simple_graph_eq_starGraph_of_forall_mem_edge- If a connected graph has a vertex r that belongs to every edge, the graph is a star graph centered at r.
Sym2.mem_mk_left- An element x belongs to the unordered pair s(x, y).
Sym2.mem_mk_right- An element y belongs to the unordered pair s(x, y).
Sym2.mem_iff- An element a belongs to s(b, c) if and only if a = b or a = c.
Sym2.mem_and_mem_iff- For distinct vertices x and y, an unordered pair z contains both x and y if and only if z = s(x, y).
Set.mem_singleton_iff- An element x belongs to {a} if and only if x = a.
- The linear arithmetic on vertex and edge counts (such as |E| = |V| - 1 from |E| + 1 = |V|) is discharged automatically by `omega`.
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_is_tree_sum_choose_degree_eq_iff_star {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hT : G.IsTree) (hk : 2 ≤ Fintype.card V) : ∑ v, (G.degree v).choose 2 = (Fintype.card V - 1).choose 2 ↔ ∃ r : V, G = SimpleGraph.starGraph r := by classical have hE : G.edgeFinset.card + 1 = Fintype.card V := hT.card_edgeFinset constructor · intro hsum -- every two distinct edges share a vertex have hmeet : ∀ e₁ ∈ G.edgeSet, ∀ e₂ ∈ G.edgeSet, e₁ ≠ e₂ → ∃ w, w ∈ e₁ ∧ w ∈ e₂ := by let S := Finset.univ.sigma (fun v => (G.incidenceFinset v).powersetCard 2) have hS : S.card = ∑ v, (G.degree v).choose 2 := by rw [Finset.card_sigma] refine Finset.sum_congr rfl fun v _ => ?_ rw [Finset.card_powersetCard, SimpleGraph.card_incidenceFinset_eq_degree] have hsub : S.image (fun p => p.2) ⊆ G.edgeFinset.powersetCard 2 := by intro t ht simp only [Finset.mem_image, S, Finset.mem_sigma, Finset.mem_univ, true_and, Finset.mem_powersetCard] at ht ⊢ obtain ⟨⟨v, t⟩, ⟨hts, htc⟩, rfl⟩ := ht exact ⟨hts.trans (SimpleGraph.incidenceFinset_subset G v), htc⟩ have hinj : Set.InjOn (fun p : (Σ _ : V, Finset (Sym2 V)) => p.2) S := by intro p hp q hq hpq simp only [Finset.coe_sigma, Set.mem_sigma_iff, Finset.mem_coe, Finset.mem_univ, true_and, Finset.mem_powersetCard, S] at hp hq obtain ⟨v, t⟩ := p obtain ⟨w, t'⟩ := q simp only at hpq hp hq subst hpq by_cases hvw : v = w · subst hvw; rfl · exfalso obtain ⟨e₁, e₂, hne, rfl⟩ := Finset.card_eq_two.1 hp.2 have h1v := hp.1 (Finset.mem_insert_self _ _) have h2v := hp.1 (Finset.mem_insert_of_mem (Finset.mem_singleton_self _)) have h1w := hq.1 (Finset.mem_insert_self _ _) have h2w := hq.1 (Finset.mem_insert_of_mem (Finset.mem_singleton_self _)) rw [SimpleGraph.mem_incidenceFinset] at h1v h2v h1w h2w apply hne have key : ∀ e ∈ G.incidenceSet v, e ∈ G.incidenceSet w → e = s(v, w) := by intro e hev hew exact (Sym2.mem_and_mem_iff hvw).1 ⟨hev.2, hew.2⟩ rw [key _ h1v h1w, key _ h2v h2w] have hcard : (S.image (fun p => p.2)).card = (G.edgeFinset.powersetCard 2).card := by rw [Finset.card_image_of_injOn hinj, hS, hsum, Finset.card_powersetCard] congr 1 omega have heq := Finset.eq_of_subset_of_card_le hsub hcard.ge intro e₁ he₁ e₂ he₂ hne have hmem : ({e₁, e₂} : Finset (Sym2 V)) ∈ G.edgeFinset.powersetCard 2 := by rw [Finset.mem_powersetCard] refine ⟨?_, Finset.card_pair hne⟩ intro e he simp only [Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl <;> simpa rw [← heq] at hmem simp only [Finset.mem_image, S, Finset.mem_sigma, Finset.mem_univ, true_and, Finset.mem_powersetCard] at hmem obtain ⟨⟨v, t⟩, ⟨hts, -⟩, rfl⟩ := hmem have h1 := hts (Finset.mem_insert_self _ _) have h2 := hts (Finset.mem_insert_of_mem (Finset.mem_singleton_self _)) rw [SimpleGraph.mem_incidenceFinset] at h1 h2 exact ⟨v, h1.2, h2.2⟩ -- an edge xy obtain ⟨x, y, hxy⟩ : ∃ x y, G.Adj x y := by obtain ⟨x, y, hne⟩ := Fintype.exists_pair_of_one_lt_card (by omega : 1 < Fintype.card V) obtain ⟨p⟩ := hT.1.preconnected x y cases p with | nil => exact absurd rfl hne | cons h _ => exact ⟨_, _, h⟩ by_cases hx : ∀ e ∈ G.edgeSet, x ∈ e · exact ⟨x, simple_graph_eq_starGraph_of_forall_mem_edge G hT.1 x hx⟩ push Not at hx obtain ⟨e₁, he₁, hxe₁⟩ := hx by_cases hy : ∀ e ∈ G.edgeSet, y ∈ e · exact ⟨y, simple_graph_eq_starGraph_of_forall_mem_edge G hT.1 y hy⟩ push Not at hy obtain ⟨e₂, he₂, hye₂⟩ := hy -- e₁ = s(y, z), e₂ = s(x, z'), and z = z' have hxy' : s(x, y) ∈ G.edgeSet := hxy obtain ⟨w₁, hw₁a, hw₁b⟩ := hmeet _ hxy' _ he₁ (fun h => hxe₁ (h ▸ Sym2.mem_mk_left x y)) obtain ⟨w₂, hw₂a, hw₂b⟩ := hmeet _ hxy' _ he₂ (fun h => hye₂ (h ▸ Sym2.mem_mk_right x y)) rw [Sym2.mem_iff] at hw₁a hw₂a have hw₁ : w₁ = y := hw₁a.resolve_left (fun h => hxe₁ (h ▸ hw₁b)) have hw₂ : w₂ = x := hw₂a.resolve_right (fun h => hye₂ (h ▸ hw₂b)) subst hw₁ hw₂ obtain ⟨z, rfl⟩ := (Sym2.mem_iff_exists.1 hw₁b) obtain ⟨z', rfl⟩ := (Sym2.mem_iff_exists.1 hw₂b) have hyz : G.Adj w₁ z := he₁ have hxz' : G.Adj w₂ z' := he₂ have hne12 : s(w₁, z) ≠ s(w₂, z') := fun h => hxe₁ (by rw [h]; exact Sym2.mem_mk_left _ _) obtain ⟨w₃, hw₃a, hw₃b⟩ := hmeet _ he₁ _ he₂ hne12 have hzz : z = z' := by rcases Sym2.mem_iff.1 hw₃a with h | h · exact absurd (h ▸ hw₃b) hye₂ · rw [h] at hw₃b rcases Sym2.mem_iff.1 hw₃b with h' | h' · exact absurd (show w₂ ∈ s(w₁, z) by rw [h']; exact Sym2.mem_mk_right _ _) hxe₁ · exact h' subst hzz -- triangle w₂ - w₁ - z contradicts acyclicity: s(w₂, z) is a bridge exfalso have hbr := (SimpleGraph.isAcyclic_iff_forall_adj_isBridge.1 hT.2) hxz' rw [SimpleGraph.isBridge_iff] at hbr apply hbr have h1 : (G.deleteEdges {s(w₂, z)}).Adj w₂ w₁ := by simp only [SimpleGraph.deleteEdges_adj, Set.mem_singleton_iff] refine ⟨hxy, fun h => ?_⟩ rcases Sym2.eq_iff.1 h with ⟨-, h'⟩ | ⟨h', h''⟩ · exact G.ne_of_adj hyz h' · exact G.ne_of_adj hxy h''.symm have h2 : (G.deleteEdges {s(w₂, z)}).Adj w₁ z := by simp only [SimpleGraph.deleteEdges_adj, Set.mem_singleton_iff] refine ⟨hyz, fun h => ?_⟩ rcases Sym2.eq_iff.1 h with ⟨h', -⟩ | ⟨h', -⟩ · exact G.ne_of_adj hxy h'.symm · exact G.ne_of_adj hyz h' exact h1.reachable.trans h2.reachable · rintro ⟨r, rfl⟩ have hc : (SimpleGraph.starGraph r).degree r = Fintype.card V - 1 := by convert SimpleGraph.degree_starGraph_center (r := r) have ho : ∀ v, v ≠ r → (SimpleGraph.starGraph r).degree v = 1 := fun v hv => by convert SimpleGraph.degree_starGraph_of_ne_center hv rw [← Finset.add_sum_erase _ _ (Finset.mem_univ r), hc, Finset.sum_eq_zero fun v hv => by rw [ho v (Finset.ne_of_mem_erase hv)]; rfl] simp