AFTD Auto-Formalizing Theoretical Domains

wiener_index_add_edges_twin_independent_set

theoremverified

Let G and H be simple graphs on a finite vertex type V, where G is connected. Suppose Z and X are subsets of V such that 2 ≤ Nat.card X, Z is an independent set in G (∀ u ∈ Z, ∀ v ∈ Z, ¬G.Adj u v), every vertex in Z has open neighborhood X in G (∀ z ∈ Z, G.neighborSet z = X), G ≤ H, and every edge of H is in G or has both endpoints in Z (∀ u v, H.Adj u v → G.Adj u v ∨ (u ∈ Z ∧ v ∈ Z)). Then the Wiener index of G equals the Wiener index of H plus the number of added edges, wiener_index G = wiener_index H + Nat.card ↑(H.edgeSet \ G.edgeSet).

Statement

theorem wiener_index_add_edges_twin_independent_set
    {V : Type*} [Fintype V]
    (G H : SimpleGraph V) (hGconn : G.Connected)
    (Z X : Set V) (hXcard : 2 ≤ Nat.card X)
    (hZindep : ∀ u ∈ Z, ∀ v ∈ Z, ¬G.Adj u v)
    (hZneigh : ∀ z ∈ Z, G.neighborSet z = X)
    (hGH_le : G ≤ H)
    (hGH_edges : ∀ u v, H.Adj u v → G.Adj u v ∨ (u ∈ Z ∧ v ∈ Z)) :
    wiener_index G = wiener_index H + Nat.card ↑(H.edgeSet \ G.edgeSet)
Source
arXiv:2611.01808 Lemma 2
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • wiener_indexThe Wiener index of a finite simple graph G is the sum of the shortest-path distances between all unordered pairs of vertices in G.

Read back from the Lean

For any finite type $V$, simple graphs $G$ and $H$ on $V$, and subsets $Z, X \subseteq V$, assume that: 1. $G$ is connected; 2. The cardinality of $X$ is at least 2; 3. $Z$ is an independent set in $G$ (no two vertices in $Z$ are adjacent in $G$); 4. Every vertex in $Z$ has the exact same open neighborhood $X$ in $G$ (for all $z \in Z$, the neighbor set of $z$ in $G$ is $X$); 5. $G \le H$ (every edge of $G$ is an edge of $H$); 6. Every edge in $H$ is either an edge of $G$ or has both endpoints in $Z$ (for all $u, v \in V$, if $u$ and $v$ are adjacent in $H$, then they are adjacent in $G$ or both $u, v \in Z$). Then the Wiener index of $G$ equals the Wiener index of $H$ plus the number of edges in $H$ that are not in $G$ (Nat.card ↑(H.edgeSet \ G.edgeSet)).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof evaluates the distance between every pair of vertices in G and H. Any walk in H connecting two vertices that do not both belong to Z can be compressed to a walk in G of equal or shorter length by replacing steps through Z with direct edges to their common neighborhood X, proving that distances are unchanged outside Z × Z. For distinct vertices in Z, their distance in G is always 2 via any common neighbor in X, whereas their distance in H drops to 1 if an edge was added between them and remains 2 otherwise. Summing this pointwise equality d_G(e) = d_H(e) + 1_{e ∈ E(H) \ E(G)} over all unordered pairs of vertices shows that the Wiener index of G exceeds that of H by exactly the number of added edges.

  1. The neighborhood X is nonempty.

    Because the cardinality of X is at least 2, X cannot be empty, as the empty set has cardinality 0.

    lines 11–14

    uses Set.nonempty_iff_ne_empty

      classical
      have hXnon : X.Nonempty := by
        rw [Set.nonempty_iff_ne_empty]
        intro h; rw [h] at hXcard; simp at hXcard
  2. Any edge of H not wholly within Z is an edge of G; any non-Z neighbor of Z in H belongs to X; and every vertex in Z is adjacent in G to every vertex in X.

    By hypothesis, every edge in H is in G or connects two vertices of Z. Thus, any edge (u, v) in H with an endpoint outside Z must already be an edge in G. Consequently, if u ∈ Z and v ∉ Z are adjacent in H, they are adjacent in G, meaning v is in the neighborhood of u in G, which is X. Conversely, because every z ∈ Z has neighborhood X in G, every vertex in Z is adjacent in G to every vertex in X.

    lines 15–30

    uses Or.inr

      have hg_of : ∀ {u v : V}, H.Adj u v → (u ∉ Z ∨ v ∉ Z) → G.Adj u v := by
        intro u v huv h
        rcases hGH_edges u v huv with hg | ⟨hu, hv⟩
        · exact hg
        · rcases h with h' | h'
          · exact absurd hu h'
          · exact absurd hv h'
      have memX_of : ∀ {u v : V}, u ∈ Z → v ∉ Z → H.Adj u v → v ∈ X := by
        intro u v hu hv huv
        have hg : G.Adj u v := hg_of huv (Or.inr hv)
        have hmem : v ∈ G.neighborSet u := hg
        rwa [hZneigh u hu] at hmem
      have adj_of_memX : ∀ {z x : V}, z ∈ Z → x ∈ X → G.Adj z x := by
        intro z x hz hx
        have hmem : x ∈ G.neighborSet z := by rw [hZneigh z hz]; exact hx
        exact hmem
  3. Any walk in H whose endpoints are not both in Z can be compressed to a walk in G of length at most the original walk.

    By strong induction on the length n of the walk p in H from a to b. The empty walk (length 0) is trivial. For a walk p = a - c - ... - b: - If a ∈ Z (so b ∉ Z): - If c ∈ Z, the walk must eventually exit Z to reach b ∉ Z. There exists a first boundary dart (z, w) exiting Z, with w ∉ Z. Since (z, w) is an H-edge with w ∉ Z, it is a G-edge and w ∈ X. Thus a is directly adjacent to w in G. Truncating p from w to b yields a strictly shorter walk s in H with w ∉ Z. By the induction hypothesis, s compresses to a G-walk q of length ≤ length(s) < length(p). Prepending the G-edge (a, w) gives a G-walk from a to b of length 1 + length(q) ≤ length(p). - If c ∉ Z, the edge (a, c) is already in G, and c ∉ Z, so the induction hypothesis applies to the tail p' from c to b, producing a G-walk of length ≤ length(p') that we prepend with (a, c). - If a ∉ Z: - If c ∈ Z, the edge (a, c) is in G, which implies a ∈ X. If b ∈ Z, then a and b are directly adjacent in G (since a ∈ X and b ∈ Z), providing a length 1 walk in G. If b ∉ Z, the induction hypothesis applies to p', and prepending (a, c) gives the required G-walk. - If c ∉ Z, the edge (a, c) is in G and c ∉ Z, so the induction hypothesis applies directly to p'.

    lines 31–85

    uses Nat.strong_induction_on, SimpleGraph.Walk.length_cons, SimpleGraph.Walk.exists_boundary_dart, SimpleGraph.Walk.dart_snd_mem_support_of_mem_darts, SimpleGraph.Walk.length_dropUntil_lt_length, Or.inr, Or.inl, SimpleGraph.Walk.length_nil

      have compress : ∀ {a b : V} (p : H.Walk a b), ¬ (a ∈ Z ∧ b ∈ Z) → ∃ q : G.Walk a b, q.length ≤ p.length := by
        suffices h : ∀ n, ∀ {a b : V} (p : H.Walk a b), p.length = n → ¬ (a ∈ Z ∧ b ∈ Z) → ∃ q : G.Walk a b, q.length ≤ p.length by
          intro a b p hp
          exact h p.length p rfl hp
        intro n
        induction n using Nat.strong_induction_on with
        | _ n ih =>
          intro a b p hpn hgood
          cases p with
          | nil => exact ⟨SimpleGraph.Walk.nil, by simp⟩
          | cons hd p' =>
            rename_i c
            have hp' : p'.length + 1 = n := by simpa only [SimpleGraph.Walk.length_cons] using hpn
            have hplen_lt : p'.length < n := by omega
            by_cases haZ : a ∈ Z
            · have hbZ : b ∉ Z := fun hb => hgood ⟨haZ, hb⟩
              by_cases hcZ : c ∈ Z
              · obtain ⟨d, hdmem, hfstZ, hsndZ⟩ := SimpleGraph.Walk.exists_boundary_dart (SimpleGraph.Walk.cons hd p') Z haZ hbZ
                have hsndX : d.toProd.2 ∈ X := memX_of hfstZ hsndZ d.adj
                have hmem : d.toProd.2 ∈ (SimpleGraph.Walk.cons hd p').support :=
                  SimpleGraph.Walk.dart_snd_mem_support_of_mem_darts _ hdmem
                have hne : d.toProd.2 ≠ a := by
                  intro heq; rw [heq] at hsndZ; exact hsndZ haZ
                set s : H.Walk d.toProd.2 b := (SimpleGraph.Walk.cons hd p').dropUntil d.toProd.2 hmem with hsdef
                have hs_lt : s.length < (SimpleGraph.Walk.cons hd p').length :=
                  SimpleGraph.Walk.length_dropUntil_lt_length hmem hne
                have hlt : s.length < n := by
                  rw [SimpleGraph.Walk.length_cons] at hs_lt; omega
                obtain ⟨q, hq⟩ := ih s.length hlt s rfl (fun h => hsndZ h.1)
                have hadj : G.Adj a d.toProd.2 := adj_of_memX haZ hsndX
                refine ⟨SimpleGraph.Walk.cons hadj q, ?_⟩
                simp only [SimpleGraph.Walk.length_cons]; omega
              · have hgood' : ¬ (c ∈ Z ∧ b ∈ Z) := fun h => hcZ h.1
                obtain ⟨q, hq⟩ := ih p'.length hplen_lt p' rfl hgood'
                have hgac : G.Adj a c := hg_of hd (Or.inr hcZ)
                refine ⟨SimpleGraph.Walk.cons hgac q, ?_⟩
                simp only [SimpleGraph.Walk.length_cons]; omega
            · by_cases hcZ : c ∈ Z
              · have hgac : G.Adj a c := hg_of hd (Or.inl haZ)
                have haX : a ∈ X := by
                  have hmem : a ∈ G.neighborSet c := hgac.symm
                  rwa [hZneigh c hcZ] at hmem
                by_cases hbZ : b ∈ Z
                · have hadj : G.Adj a b := (adj_of_memX hbZ haX).symm
                  refine ⟨SimpleGraph.Walk.cons hadj SimpleGraph.Walk.nil, ?_⟩
                  simp only [SimpleGraph.Walk.length_cons, SimpleGraph.Walk.length_nil]; omega
                · have hgood' : ¬ (c ∈ Z ∧ b ∈ Z) := fun h => hbZ h.2
                  obtain ⟨q, hq⟩ := ih p'.length hplen_lt p' rfl hgood'
                  refine ⟨SimpleGraph.Walk.cons hgac q, ?_⟩
                  simp only [SimpleGraph.Walk.length_cons]; omega
              · have hgood' : ¬ (c ∈ Z ∧ b ∈ Z) := fun h => hcZ h.1
                obtain ⟨q, hq⟩ := ih p'.length hplen_lt p' rfl hgood'
                have hgac : G.Adj a c := hg_of hd (Or.inl haZ)
                refine ⟨SimpleGraph.Walk.cons hgac q, ?_⟩
                simp only [SimpleGraph.Walk.length_cons]; omega
  4. For any pair of vertices not both in Z, their distance in G equals their distance in H.

    Since G is connected and G ≤ H, H is also connected. Because adding edges cannot increase distances, H.dist(u, v) ≤ G.dist(u, v). Conversely, taking a shortest walk p in H from u to v of length H.dist(u, v), the compression property produces a walk q in G between u and v with length ≤ length(p) = H.dist(u, v). Since the distance in G is at most the length of any walk in G, G.dist(u, v) ≤ H.dist(u, v). By antisymmetry, the two distances are equal.

    lines 86–95

    uses le_antisymm, SimpleGraph.dist_le, SimpleGraph.Reachable.dist_anti

      have hHconn : H.Connected := hGconn.mono hGH_le
      have hdist_eq : ∀ {u v : V}, ¬ (u ∈ Z ∧ v ∈ Z) → G.dist u v = H.dist u v := by
        intro u v hgood
        refine le_antisymm ?_ ?_
        · obtain ⟨p, hp⟩ := hHconn.exists_walk_length_eq_dist u v
          obtain ⟨q, hq⟩ := compress p hgood
          calc G.dist u v ≤ q.length := SimpleGraph.dist_le q
            _ ≤ p.length := hq
            _ = H.dist u v := hp
        · exact SimpleGraph.Reachable.dist_anti hGH_le (hGconn u v)
  5. Any two distinct vertices in Z are at distance 2 in G.

    Because Z is an independent set in G, distinct vertices u, v ∈ Z are not adjacent, so their distance in G is strictly greater than 1. Since X is nonempty, there exists some x ∈ X. Both u and v are adjacent to x in G, so the two-step walk u - x - v shows G.dist(u, v) ≤ 2. Together, 1 < G.dist(u, v) ≤ 2 implies G.dist(u, v) = 2.

    lines 96–107

    uses SimpleGraph.dist_le

      have G_dist_two : ∀ {u v : V}, u ∈ Z → v ∈ Z → u ≠ v → G.dist u v = 2 := by
        intro u v hu hv hne
        have hnadj : ¬ G.Adj u v := hZindep u hu v hv
        have hgt : 1 < G.dist u v := hGconn.one_lt_dist_of_ne_of_not_adj hne hnadj
        have hle : G.dist u v ≤ 2 := by
          obtain ⟨x, hx⟩ := hXnon
          have h1 : G.Adj u x := adj_of_memX hu hx
          have h2 : G.Adj v x := adj_of_memX hv hx
          have hw : G.dist u v ≤ (SimpleGraph.Walk.cons h1 (SimpleGraph.Walk.cons h2.symm SimpleGraph.Walk.nil)).length :=
            SimpleGraph.dist_le _
          simpa using hw
        omega
  6. For every unordered pair of vertices e, the distance in G equals the distance in H plus 1 if e is an edge added in H \ G, and equals the distance in H otherwise.

    We analyze an unordered pair e = {u, v}: - If {u, v} ∈ E(H) \ E(G), then u and v are adjacent in H but not in G. By the hypothesis on added edges, both u, v ∈ Z, and since they are adjacent in H, u ≠ v. Thus G.dist(u, v) = 2, while H.dist(u, v) = 1 (since they are adjacent in H), so G.dist(u, v) = H.dist(u, v) + 1. - If {u, v} ∉ E(H) \ E(G): - If both u, v ∈ Z: they cannot be adjacent in H (otherwise {u, v} would be an edge of H \ G, since Z is independent in G). If u = v, both distances are 0. If u ≠ v, G.dist(u, v) = 2; in H, since u and v are nonadjacent and distinct, H.dist(u, v) > 1, and H.dist(u, v) ≤ G.dist(u, v) = 2, so H.dist(u, v) = 2 = G.dist(u, v). - If not both u, v ∈ Z, G.dist(u, v) = H.dist(u, v) was established in the distance preservation step.

    lines 108–136

    uses Sym2.ind, SimpleGraph.mem_edgeSet, if_pos, SimpleGraph.dist_eq_one_iff_adj, if_neg, SimpleGraph.Reachable.dist_anti

      have hpoint : ∀ e : Sym2 V,
          Sym2.lift ⟨fun a b => G.dist a b, fun _ _ => G.dist_comm⟩ e =
          Sym2.lift ⟨fun a b => H.dist a b, fun _ _ => H.dist_comm⟩ e + (if e ∈ H.edgeSet \ G.edgeSet then 1 else 0) := by
          intro e
          induction e using Sym2.ind with
          | _ u v =>
            show G.dist u v = H.dist u v + (if Sym2.mk u v ∈ H.edgeSet \ G.edgeSet then 1 else 0)
            by_cases hnew : Sym2.mk u v ∈ H.edgeSet \ G.edgeSet
            · have hHad : H.Adj u v := (SimpleGraph.mem_edgeSet H).mp hnew.1
              have hnGad : ¬ G.Adj u v := fun hg => hnew.2 ((SimpleGraph.mem_edgeSet G).mpr hg)
              obtain ⟨hu, hv⟩ := (hGH_edges u v hHad).resolve_left hnGad
              have hne : u ≠ v := hHad.ne
              rw [if_pos hnew, G_dist_two hu hv hne, SimpleGraph.dist_eq_one_iff_adj.mpr hHad]
            · rw [if_neg hnew]
              by_cases hbothZ : u ∈ Z ∧ v ∈ Z
              · have hHad : ¬ H.Adj u v := by
                  intro hHad
                  have hnG : ¬ G.Adj u v := hZindep u hbothZ.1 v hbothZ.2
                  exact hnew ⟨(SimpleGraph.mem_edgeSet H).mpr hHad, fun h => hnG ((SimpleGraph.mem_edgeSet G).mp h)⟩
                by_cases hne : u = v
                · subst hne; simp
                · rw [G_dist_two hbothZ.1 hbothZ.2 hne]
                  have hle : H.dist u v ≤ 2 := by
                    have h := SimpleGraph.Reachable.dist_anti hGH_le (hGconn u v)
                    rw [G_dist_two hbothZ.1 hbothZ.2 hne] at h
                    exact h
                  have hgt : 1 < H.dist u v := hHconn.one_lt_dist_of_ne_of_not_adj hne hHad
                  omega
              · exact hdist_eq hbothZ
  7. The number of added edges equals the sum over all unordered pairs of the indicator that the pair belongs to E(H) \ E(G).

    The cardinality of the edge difference set is rewritten as the size of the corresponding filtered finset of unordered pairs, which equals the sum over all pairs of 1 if the pair is an added edge and 0 otherwise.

    lines 137–138

    uses Nat.card_eq_fintype_card, Fintype.card_subtype, Finset.card_filter

      have hcard : Nat.card ↑(H.edgeSet \ G.edgeSet) = ∑ e : Sym2 V, (if e ∈ H.edgeSet \ G.edgeSet then 1 else 0) := by
        rw [Nat.card_eq_fintype_card, Fintype.card_subtype, Finset.card_filter]
  8. Summing the pointwise distance equality over all unordered pairs decomposes the Wiener index of G into the Wiener index of H plus the number of added edges.

    By definition, the Wiener index is the sum of graph distances over all unordered pairs of vertices. Replacing each distance G.dist(e) with H.dist(e) plus the indicator of whether e is an added edge, and distributing the summation, yields the Wiener index of H plus the sum of indicator values, which equals the number of edges in E(H) \ E(G).

    lines 139–143

    uses Finset.sum_congr, Finset.sum_add_distrib

      simp only [wiener_index]
      have hsum : (∑ e : Sym2 V, Sym2.lift ⟨fun a b => G.dist a b, fun _ _ => G.dist_comm⟩ e)
          = ∑ e : Sym2 V, (Sym2.lift ⟨fun a b => H.dist a b, fun _ _ => H.dist_comm⟩ e + (if e ∈ H.edgeSet \ G.edgeSet then 1 else 0)) :=
        Finset.sum_congr rfl (fun e _ => hpoint e)
      rw [hsum, Finset.sum_add_distrib, hcard]
Finset.sum_add_distrib
The sum of a sum of functions over a finite set equals the sum of the individual sums.
Finset.sum_congr
Two sums over equal finite sets are equal if their summands agree on every element.
Finset.card_filter
The cardinality of a filtered finite set equals the sum of the indicator function of the filter condition over the set.
Fintype.card_subtype
The cardinality of a subtype defined by a predicate on a finite type equals the cardinality of the filtered finset of elements satisfying the predicate.
Nat.card_eq_fintype_card
The cardinality of a finite type as a natural number equals the size of its Fintype instance.
Nat.strong_induction_on
Strong induction principle for natural numbers: to prove P(n) for all n, it suffices to prove P(n) under the hypothesis that P(m) holds for all m < n.
Or.inl
If proposition A holds, then the disjunction A ∨ B holds.
Or.inr
If proposition B holds, then the disjunction A ∨ B holds.
Set.nonempty_iff_ne_empty
A set is nonempty if and only if it is not equal to the empty set.
SimpleGraph.Reachable.dist_anti
Adding edges to a graph does not increase the distance between reachable vertices.
SimpleGraph.dist_eq_one_iff_adj
Two vertices in a graph have distance 1 if and only if they are adjacent.
SimpleGraph.dist_le
The distance between two vertices in a graph is bounded above by the length of any walk connecting them.
SimpleGraph.Walk.dart_snd_mem_support_of_mem_darts
The target vertex of any dart appearing in a walk belongs to the sequence of vertices visited by the walk.
SimpleGraph.Walk.exists_boundary_dart
In any walk from a vertex in S to a vertex outside S, there exists a step (dart) whose source is in S and whose target is outside S.
SimpleGraph.Walk.length_cons
Prepending an edge to a walk increases its length by 1.
SimpleGraph.Walk.length_dropUntil_lt_length
Truncating a walk at a vertex strictly after its start produces a walk of strictly smaller length.
SimpleGraph.Walk.length_nil
The empty walk at any vertex has length 0.
Sym2.ind
Induction principle for unordered pairs: a property holds for all unordered pairs if it holds for pairs of the form {x, y}.
SimpleGraph.mem_edgeSet
An unordered pair {u, v} belongs to the edge set of a graph if and only if u and v are adjacent.
if_neg
If a condition is false, the conditional expression if c then t else e evaluates to e.
if_pos
If a condition is true, the conditional expression if c then t else e evaluates to t.
le_antisymm
If a ≤ b and b ≤ a in a partial order, then a = b.

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

/-- Adding edges between twin independent vertices reduces the Wiener index by the number of added edges. -/theorem wiener_index_add_edges_twin_independent_set    {V : Type*} [Fintype V]    (G H : SimpleGraph V) (hGconn : G.Connected)    (Z X : Set V) (hXcard : 2 ≤ Nat.card X)    (hZindep : ∀ u ∈ Z, ∀ v ∈ Z, ¬G.Adj u v)    (hZneigh : ∀ z ∈ Z, G.neighborSet z = X)    (hGH_le : G ≤ H)    (hGH_edges : ∀ u v, H.Adj u v → G.Adj u v ∨ (u ∈ Z ∧ v ∈ Z)) :    wiener_index G = wiener_index H + Nat.card ↑(H.edgeSet \ G.edgeSet) := by  classical  have hXnon : X.Nonempty := by    rw [Set.nonempty_iff_ne_empty]    intro h; rw [h] at hXcard; simp at hXcard  have hg_of : ∀ {u v : V}, H.Adj u v → (u ∉ Z ∨ v ∉ Z) → G.Adj u v := by    intro u v huv h    rcases hGH_edges u v huv with hg | ⟨hu, hv⟩    · exact hg    · rcases h with h' | h'      · exact absurd hu h'      · exact absurd hv h'  have memX_of : ∀ {u v : V}, u ∈ Z → v ∉ Z → H.Adj u v → v ∈ X := by    intro u v hu hv huv    have hg : G.Adj u v := hg_of huv (Or.inr hv)    have hmem : v ∈ G.neighborSet u := hg    rwa [hZneigh u hu] at hmem  have adj_of_memX : ∀ {z x : V}, z ∈ Z → x ∈ X → G.Adj z x := by    intro z x hz hx    have hmem : x ∈ G.neighborSet z := by rw [hZneigh z hz]; exact hx    exact hmem  have compress : ∀ {a b : V} (p : H.Walk a b), ¬ (a ∈ Z ∧ b ∈ Z) → ∃ q : G.Walk a b, q.length ≤ p.length := by    suffices h : ∀ n, ∀ {a b : V} (p : H.Walk a b), p.length = n → ¬ (a ∈ Z ∧ b ∈ Z) → ∃ q : G.Walk a b, q.length ≤ p.length by      intro a b p hp      exact h p.length p rfl hp    intro n    induction n using Nat.strong_induction_on with    | _ n ih =>      intro a b p hpn hgood      cases p with      | nil => exact ⟨SimpleGraph.Walk.nil, by simp⟩      | cons hd p' =>        rename_i c        have hp' : p'.length + 1 = n := by simpa only [SimpleGraph.Walk.length_cons] using hpn        have hplen_lt : p'.length < n := by omega        by_cases haZ : a ∈ Z        · have hbZ : b ∉ Z := fun hb => hgood ⟨haZ, hb⟩          by_cases hcZ : c ∈ Z          · obtain ⟨d, hdmem, hfstZ, hsndZ⟩ := SimpleGraph.Walk.exists_boundary_dart (SimpleGraph.Walk.cons hd p') Z haZ hbZ            have hsndX : d.toProd.2 ∈ X := memX_of hfstZ hsndZ d.adj            have hmem : d.toProd.2 ∈ (SimpleGraph.Walk.cons hd p').support :=              SimpleGraph.Walk.dart_snd_mem_support_of_mem_darts _ hdmem            have hne : d.toProd.2 ≠ a := by              intro heq; rw [heq] at hsndZ; exact hsndZ haZ            set s : H.Walk d.toProd.2 b := (SimpleGraph.Walk.cons hd p').dropUntil d.toProd.2 hmem with hsdef            have hs_lt : s.length < (SimpleGraph.Walk.cons hd p').length :=              SimpleGraph.Walk.length_dropUntil_lt_length hmem hne            have hlt : s.length < n := by              rw [SimpleGraph.Walk.length_cons] at hs_lt; omega            obtain ⟨q, hq⟩ := ih s.length hlt s rfl (fun h => hsndZ h.1)            have hadj : G.Adj a d.toProd.2 := adj_of_memX haZ hsndX            refine ⟨SimpleGraph.Walk.cons hadj q, ?_⟩            simp only [SimpleGraph.Walk.length_cons]; omega          · have hgood' : ¬ (c ∈ Z ∧ b ∈ Z) := fun h => hcZ h.1            obtain ⟨q, hq⟩ := ih p'.length hplen_lt p' rfl hgood'            have hgac : G.Adj a c := hg_of hd (Or.inr hcZ)            refine ⟨SimpleGraph.Walk.cons hgac q, ?_⟩            simp only [SimpleGraph.Walk.length_cons]; omega        · by_cases hcZ : c ∈ Z          · have hgac : G.Adj a c := hg_of hd (Or.inl haZ)            have haX : a ∈ X := by              have hmem : a ∈ G.neighborSet c := hgac.symm              rwa [hZneigh c hcZ] at hmem            by_cases hbZ : b ∈ Z            · have hadj : G.Adj a b := (adj_of_memX hbZ haX).symm              refine ⟨SimpleGraph.Walk.cons hadj SimpleGraph.Walk.nil, ?_⟩              simp only [SimpleGraph.Walk.length_cons, SimpleGraph.Walk.length_nil]; omega            · have hgood' : ¬ (c ∈ Z ∧ b ∈ Z) := fun h => hbZ h.2              obtain ⟨q, hq⟩ := ih p'.length hplen_lt p' rfl hgood'              refine ⟨SimpleGraph.Walk.cons hgac q, ?_⟩              simp only [SimpleGraph.Walk.length_cons]; omega          · have hgood' : ¬ (c ∈ Z ∧ b ∈ Z) := fun h => hcZ h.1            obtain ⟨q, hq⟩ := ih p'.length hplen_lt p' rfl hgood'            have hgac : G.Adj a c := hg_of hd (Or.inl haZ)            refine ⟨SimpleGraph.Walk.cons hgac q, ?_⟩            simp only [SimpleGraph.Walk.length_cons]; omega  have hHconn : H.Connected := hGconn.mono hGH_le  have hdist_eq : ∀ {u v : V}, ¬ (u ∈ Z ∧ v ∈ Z) → G.dist u v = H.dist u v := by    intro u v hgood    refine le_antisymm ?_ ?_    · obtain ⟨p, hp⟩ := hHconn.exists_walk_length_eq_dist u v      obtain ⟨q, hq⟩ := compress p hgood      calc G.dist u v ≤ q.length := SimpleGraph.dist_le q        _ ≤ p.length := hq        _ = H.dist u v := hp    · exact SimpleGraph.Reachable.dist_anti hGH_le (hGconn u v)  have G_dist_two : ∀ {u v : V}, u ∈ Z → v ∈ Z → u ≠ v → G.dist u v = 2 := by    intro u v hu hv hne    have hnadj : ¬ G.Adj u v := hZindep u hu v hv    have hgt : 1 < G.dist u v := hGconn.one_lt_dist_of_ne_of_not_adj hne hnadj    have hle : G.dist u v ≤ 2 := by      obtain ⟨x, hx⟩ := hXnon      have h1 : G.Adj u x := adj_of_memX hu hx      have h2 : G.Adj v x := adj_of_memX hv hx      have hw : G.dist u v ≤ (SimpleGraph.Walk.cons h1 (SimpleGraph.Walk.cons h2.symm SimpleGraph.Walk.nil)).length :=        SimpleGraph.dist_le _      simpa using hw    omega  have hpoint : ∀ e : Sym2 V,      Sym2.lift ⟨fun a b => G.dist a b, fun _ _ => G.dist_comm⟩ e =      Sym2.lift ⟨fun a b => H.dist a b, fun _ _ => H.dist_comm⟩ e + (if e ∈ H.edgeSet \ G.edgeSet then 1 else 0) := by      intro e      induction e using Sym2.ind with      | _ u v =>        show G.dist u v = H.dist u v + (if Sym2.mk u v ∈ H.edgeSet \ G.edgeSet then 1 else 0)        by_cases hnew : Sym2.mk u v ∈ H.edgeSet \ G.edgeSet        · have hHad : H.Adj u v := (SimpleGraph.mem_edgeSet H).mp hnew.1          have hnGad : ¬ G.Adj u v := fun hg => hnew.2 ((SimpleGraph.mem_edgeSet G).mpr hg)          obtain ⟨hu, hv⟩ := (hGH_edges u v hHad).resolve_left hnGad          have hne : u ≠ v := hHad.ne          rw [if_pos hnew, G_dist_two hu hv hne, SimpleGraph.dist_eq_one_iff_adj.mpr hHad]        · rw [if_neg hnew]          by_cases hbothZ : u ∈ Z ∧ v ∈ Z          · have hHad : ¬ H.Adj u v := by              intro hHad              have hnG : ¬ G.Adj u v := hZindep u hbothZ.1 v hbothZ.2              exact hnew ⟨(SimpleGraph.mem_edgeSet H).mpr hHad, fun h => hnG ((SimpleGraph.mem_edgeSet G).mp h)⟩            by_cases hne : u = v            · subst hne; simp            · rw [G_dist_two hbothZ.1 hbothZ.2 hne]              have hle : H.dist u v ≤ 2 := by                have h := SimpleGraph.Reachable.dist_anti hGH_le (hGconn u v)                rw [G_dist_two hbothZ.1 hbothZ.2 hne] at h                exact h              have hgt : 1 < H.dist u v := hHconn.one_lt_dist_of_ne_of_not_adj hne hHad              omega          · exact hdist_eq hbothZ  have hcard : Nat.card ↑(H.edgeSet \ G.edgeSet) = ∑ e : Sym2 V, (if e ∈ H.edgeSet \ G.edgeSet then 1 else 0) := by    rw [Nat.card_eq_fintype_card, Fintype.card_subtype, Finset.card_filter]  simp only [wiener_index]  have hsum : (∑ e : Sym2 V, Sym2.lift ⟨fun a b => G.dist a b, fun _ _ => G.dist_comm⟩ e)      = ∑ e : Sym2 V, (Sym2.lift ⟨fun a b => H.dist a b, fun _ _ => H.dist_comm⟩ e + (if e ∈ H.edgeSet \ G.edgeSet then 1 else 0)) :=    Finset.sum_congr rfl (fun e _ => hpoint e)  rw [hsum, Finset.sum_add_distrib, hcard]
See it in the graphDiscuss this resultChallenge it