AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_tree_sum_choose_degree_eq_iff_star

theoremverifiedformalization

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
Used by 1

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.

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

    lines 6–8

      classical
      have hE : G.edgeFinset.card + 1 = Fintype.card V := hT.card_edgeFinset
      constructor
  2. 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.

    lines 9–64

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

    lines 65–71

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

    lines 72–79

    uses simple_graph_eq_starGraph_of_forall_mem_edge

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

    lines 80–102

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

    lines 103–120

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

    lines 121–128

    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.

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