wiener_index_add_edges_twin_independent_set
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.
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.
uses
Set.nonempty_iff_ne_emptyclassical have hXnon : X.Nonempty := by rw [Set.nonempty_iff_ne_empty] intro h; rw [h] at hXcard; simp at hXcard
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.
uses
Or.inrhave 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
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'.
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_nilhave 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
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.
uses
le_antisymm,SimpleGraph.dist_le,SimpleGraph.Reachable.dist_antihave 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)
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.
uses
SimpleGraph.dist_lehave 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
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.
uses
Sym2.ind,SimpleGraph.mem_edgeSet,if_pos,SimpleGraph.dist_eq_one_iff_adj,if_neg,SimpleGraph.Reachable.dist_antihave 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
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.
uses
Nat.card_eq_fintype_card,Fintype.card_subtype,Finset.card_filterhave 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]
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).
uses
Finset.sum_congr,Finset.sum_add_distribsimp 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.
- Unordered pairs of vertices are formally represented using the quotient type Sym2 V, over which the Wiener index is defined as a sum.
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.
/-- 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]