exists_dist_three_lly_curvature_le_cut_interior
If x lies in the interior of X (all its neighbours in X) and y in the interior of Xᶜ, and d(x,y) = 3, then κ_LLY(x,y) ≤ 2·|E(X,Xᶜ)| / (3 δ(G)).
Statement
theorem exists_dist_three_lly_curvature_le_cut_interior {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (X : Finset V) (x y : V) (hxX : x ∈ X) (hxint : ∀ w : V, G.Adj x w → w ∈ X) (hyX : y ∈ (Xᶜ : Finset V)) (hyint : ∀ w : V, G.Adj y w → w ∈ (Xᶜ : Finset V)) (hd3 : G.dist x y = 3) : graph_lly_curvature G x y ≤ (2 * ((G.edgeFinset.filter (fun e => ∃ u ∈ X, ∃ v ∈ (Xᶜ : Finset V), e = s(u, v))).card : ℝ)) / (3 * (G.minDegree : ℝ))
- Source
- step towards exists_dist_three_lly_curvature_le_cut
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- graph_lly_curvature_le_of_lipschitz_cut_potentialKantorovich-duality bound on the Lin–Lu–Yau curvature at a pair: for x ≠ y and any 1-Lipschitz potential f with f(x) − f(y) = d(x,y),…
- graph_lly_curvatureThe Lin–Lu–Yau curvature κ_LLY(x, y) = lim_{α → 1⁻} κ_α(x, y)/(1 − α).
- graph_lly_curvature_commThe Lin–Lu–Yau curvature is symmetric: κ_LLY(x, y) = κ_LLY(y, x).
The proof, explained
The proof bounds the Lin–Lu–Yau (LLY) curvature $\kappa_{\mathrm{LLY}}(x, y)$ between interior vertices $x \in X$ and $y \in X^c$ at distance 3 using the 1-Lipschitz potential function $f(v) = \operatorname{dist}(v, X_2)$, where $X_2$ is the interior of $X$. Since $f(x) = 0$ and $f(y) = 3 = \operatorname{dist}(y, x)$, a general cut-potential inequality bounds $\kappa_{\mathrm{LLY}}(y, x)$ by $\frac{1}{3}\left( \frac{1}{\deg y}\sum_{b \sim y}(3 - f(b)) + \frac{1}{\deg x}\sum_{a \sim x} f(a) \right)$. The local variations around $x$ and $y$ are then bounded by counting boundary neighbor sets $S_1 \subseteq N(x)$ and $S_2 \subseteq N(y)$, each of which injects into the cut edges $C = E(X, X^c)$. Finally, bounding vertex degrees from below by the minimum degree $\delta(G)$ and invoking the symmetry of LLY curvature yields $\kappa_{\mathrm{LLY}}(x, y) \le \frac{2|C|}{3\delta(G)}$.
Define the interior $X_2 \subseteq X$ and the potential function $f(v) = \operatorname{dist}(v, X_2)$.
We define $X_2 \subseteq X$ as the set of vertices in $X$ whose neighbors all lie in $X$. Since $x \in X$ and all its neighbors lie in $X$, $x \in X_2$, so $X_2$ is nonempty. We then define $f(v) = \min_{z \in X_2} \operatorname{dist}(v, z)$ as the distance from $v$ to $X_2$.
uses
Finset.mem_filterclassical set X2 : Finset V := X.filter (fun z => ∀ w : V, G.Adj z w → w ∈ X) with hX2def have hX2sub : ∀ z ∈ X2, z ∈ X ∧ ∀ w : V, G.Adj z w → w ∈ X := by intro z hz; rw [hX2def, Finset.mem_filter] at hz; exact hz have hxX2 : x ∈ X2 := by rw [hX2def, Finset.mem_filter]; exact ⟨hxX, hxint⟩ have hX2ne : X2.Nonempty := ⟨x, hxX2⟩ let f : V → ℝ := fun v => ((X2.inf' hX2ne (fun z => G.dist v z) : ℕ) : ℝ) have hfval : ∀ v : V, f v = ((X2.inf' hX2ne (fun z => G.dist v z) : ℕ) : ℝ) := fun v => rfl
Define the cut $C = E(X, X^c)$, boundary neighbor sets $S_2 \subseteq N(y)$ and $S_1 \subseteq N(x)$, and note $x \ne y$.
We let $C$ be the set of cut edges with one endpoint in $X$ and one in $X^c$. We set $S_2 = \{b \in N(y) \mid f(b) = 2\}$ and $S_1 = \{a \in N(x) \mid a \notin X_2\}$. Since $\operatorname{dist}(x, y) = 3 \ne 0$, $x \ne y$.
uses
SimpleGraph.dist_selfset C : Finset (Sym2 V) := G.edgeFinset.filter (fun e => ∃ u ∈ X, ∃ v ∈ (Xᶜ : Finset V), e = s(u, v)) with hC set S2 : Finset V := (G.neighborFinset y).filter (fun b => f b = 2) with hS2 set S1 : Finset V := (G.neighborFinset x).filter (fun a => a ∉ X2) with hS1 have hxy : x ≠ y := by intro h; rw [h, SimpleGraph.dist_self] at hd3; omega
$f(x) = 0$.
Because $x \in X_2$, the distance $\operatorname{dist}(x, x) = 0$ provides an upper bound on $\inf_{z \in X_2} \operatorname{dist}(x, z)$, and since distances are non-negative, the infimum is exactly 0.
uses
Finset.inf'_le,SimpleGraph.dist_self,Nat.zero_le,le_antisymmhave hfx : f x = 0 := by have h1 : X2.inf' hX2ne (fun z => G.dist x z) ≤ G.dist x x := Finset.inf'_le _ hxX2 rw [SimpleGraph.dist_self] at h1 have h2 : (0:ℕ) ≤ X2.inf' hX2ne (fun z => G.dist x z) := Nat.zero_le _ have hinf : X2.inf' hX2ne (fun z => G.dist x z) = 0 := le_antisymm h1 h2 rw [hfval, hinf]; norm_num
For every $z \in X_2$, $\operatorname{dist}(y, z) \ge 3$.
Suppose for contradiction that $\operatorname{dist}(y, z) < 3$ for some $z \in X_2$. Since $z \in X$ and $y \in X^c$, $z \ne y$, so $\operatorname{dist}(y, z)$ is either 1 or 2. If $\operatorname{dist}(y, z) = 1$, then $y \sim z$, which contradicts the assumption that all neighbors of $y$ lie in $X^c$. If $\operatorname{dist}(y, z) = 2$, there is a path $y \sim c \sim z$; then $y \sim c$ forces $c \in X^c$, while $z \sim c$ forces $c \in X$ because $z \in X_2$, a contradiction.
uses
Finset.mem_compl,SimpleGraph.dist_ne_zero_iff_ne_and_reachable,SimpleGraph.dist_eq_one_iff_adjhave hge : ∀ z ∈ X2, 3 ≤ G.dist y z := by intro z hz obtain ⟨hzX, hzint⟩ := hX2sub z hz by_contra hlt push Not at hlt have hzy : z ≠ y := by intro h; rw [h] at hzX; rw [Finset.mem_compl] at hyX; exact hyX hzX have hyz_ne : G.dist y z ≠ 0 := by rw [SimpleGraph.dist_ne_zero_iff_ne_and_reachable] exact ⟨fun h => hzy h.symm, hG y z⟩ have : G.dist y z = 1 ∨ G.dist y z = 2 := by omega rcases this with h1 | h2 · have hadj : G.Adj y z := by rw [← SimpleGraph.dist_eq_one_iff_adj, h1] have hzc : z ∈ (Xᶜ : Finset V) := hyint z hadj rw [Finset.mem_compl] at hzc; exact hzc hzX · obtain ⟨p, hp⟩ := hG.exists_walk_length_eq_dist y z have hp2 : p.length = 2 := by rw [hp, h2] have hadjyc : G.Adj y (p.getVert 1) := by have := p.adj_getVert_succ (i := 0) (by rw [hp2]; omega); simpa using this have hadjcz : G.Adj z (p.getVert 1) := by have h := p.adj_getVert_succ (i := 1) (by rw [hp2]; omega) have h2' : p.getVert 2 = z := by rw [← hp2]; exact p.getVert_length rw [h2'] at h; exact h.symm have hcXc : p.getVert 1 ∈ (Xᶜ : Finset V) := hyint _ hadjyc rw [Finset.mem_compl] at hcXc exact hcXc (hzint _ hadjcz)
$f(y) = 3$.
Since $x \in X_2$ and $\operatorname{dist}(y, x) = 3$, $f(y) \le 3$. Conversely, every $z \in X_2$ satisfies $\operatorname{dist}(y, z) \ge 3$, so $f(y) \ge 3$, proving $f(y) = 3$.
uses
Finset.inf'_le,SimpleGraph.dist_comm,Finset.le_inf',le_antisymmhave hfy : f y = 3 := by have hle : X2.inf' hX2ne (fun z => G.dist y z) ≤ 3 := by have := Finset.inf'_le (fun z => G.dist y z) hxX2 rwa [SimpleGraph.dist_comm, hd3] at this have hge' : 3 ≤ X2.inf' hX2ne (fun z => G.dist y z) := Finset.le_inf' hX2ne _ hge have hinf : X2.inf' hX2ne (fun z => G.dist y z) = 3 := le_antisymm hle hge' rw [hfval, hinf]; norm_num
The potential $f$ is 1-Lipschitz: $f(a) - f(b) \le \operatorname{dist}(a, b)$ for all $a, b \in V$.
For any $b$, choose a minimizer $z_0 \in X_2$ achieving $f(b) = \operatorname{dist}(b, z_0)$. By the triangle inequality, $f(a) \le \operatorname{dist}(a, z_0) \le \operatorname{dist}(a, b) + \operatorname{dist}(b, z_0) = \operatorname{dist}(a, b) + f(b)$, which rearranges to $f(a) - f(b) \le \operatorname{dist}(a, b)$.
uses
Finset.exists_mem_eq_inf',Finset.inf'_le,SimpleGraph.Reachable.dist_triangle_left,Nat.cast_le,Nat.cast_addhave hf : ∀ a b : V, f a - f b ≤ (G.dist a b : ℝ) := by intro a b obtain ⟨z0, hz0mem, hz0eq⟩ := Finset.exists_mem_eq_inf' hX2ne (fun z => G.dist b z) have h1 : X2.inf' hX2ne (fun z => G.dist a z) ≤ G.dist a z0 := Finset.inf'_le _ hz0mem have h2 : G.dist a z0 ≤ G.dist a b + G.dist b z0 := SimpleGraph.Reachable.dist_triangle_left (hG a b) z0 have hds : X2.inf' hX2ne (fun z => G.dist a z) ≤ X2.inf' hX2ne (fun z => G.dist b z) + G.dist a b := by rw [hz0eq]; omega have hcast : ((X2.inf' hX2ne (fun z => G.dist a z) : ℕ) : ℝ) ≤ ((X2.inf' hX2ne (fun z => G.dist b z) : ℕ) : ℝ) + (G.dist a b : ℝ) := by have hc := (Nat.cast_le (α := ℝ)).mpr hds; rw [Nat.cast_add] at hc; exact hc rw [hfval, hfval] linarith
Every neighbor $b$ of $y$ satisfies $f(b) \ge 2$.
Any neighbor $b$ of $y$ lies in $X^c$. For any $z \in X_2 \subseteq X$, $b \ne z$. Moreover, $b$ cannot be adjacent to $z$ because all neighbors of $z \in X_2$ belong to $X$. Hence $\operatorname{dist}(b, z) \ge 2$ for all $z \in X_2$, so $f(b) \ge 2$.
uses
SimpleGraph.mem_neighborFinset,Finset.mem_compl,SimpleGraph.dist_ne_zero_iff_ne_and_reachable,SimpleGraph.dist_comm,SimpleGraph.dist_eq_one_iff_adj,Finset.le_inf'have h2le : ∀ b ∈ G.neighborFinset y, (2:ℝ) ≤ f b := by intro b hb have hyb : G.Adj y b := (SimpleGraph.mem_neighborFinset G y b).mp hb have hbXc : b ∉ X := by have := hyint b hyb; rwa [Finset.mem_compl] at this have hge2 : ∀ z ∈ X2, 2 ≤ G.dist b z := by intro z hz obtain ⟨hzX, hzint⟩ := hX2sub z hz have hbz : b ≠ z := by intro h; exact hbXc (h ▸ hzX) have hne0 : G.dist b z ≠ 0 := by rw [SimpleGraph.dist_ne_zero_iff_ne_and_reachable] exact ⟨hbz, hG b z⟩ have hne1 : G.dist b z ≠ 1 := by intro h have hzb : G.dist z b = 1 := by rw [SimpleGraph.dist_comm]; exact h exact hbXc (hzint b (SimpleGraph.dist_eq_one_iff_adj.mp hzb)) omega have := Finset.le_inf' hX2ne (fun z => G.dist b z) hge2 rw [hfval] exact_mod_cast this
$|S_2| \le |C|$.
For each $b \in S_2$, $f(b) = 2$, so there is a 2-step path $b \sim c \sim z$ to some $z \in X_2$. The vertex $c$ is adjacent to $z \in X_2$, hence $c \in X$. Since $b \in N(y) \subseteq X^c$, the edge $\{c, b\}$ belongs to the cut $C$. Choosing such a neighbor $c$ for each $b$ defines a map $\phi : S_2 \to C$. This map is injective because in $\{c, b\} \in C$, $b$ is the unique endpoint lying in $X^c$, so $|S_2| \le |C|$.
uses
Finset.mem_filter,Finset.exists_mem_eq_inf',Finset.card_le_card_of_injOn,SimpleGraph.mem_neighborFinset,Finset.mem_compl,dif_pos,Finset.mem_coe,SimpleGraph.mem_edgeFinset,SimpleGraph.mem_edgeSet,Sym2.eq_iffhave hS2k : S2.card ≤ C.card := by have hex : ∀ b ∈ S2, ∃ c : V, G.Adj b c ∧ c ∈ X := by intro b hb rw [hS2, Finset.mem_filter] at hb obtain ⟨hbN, hfb⟩ := hb obtain ⟨z, hzmem, hzeq⟩ := Finset.exists_mem_eq_inf' hX2ne (fun z => G.dist b z) have hcast : ((X2.inf' hX2ne (fun z => G.dist b z) : ℕ) : ℝ) = 2 := by rw [← hfval b]; exact hfb have hdseq : X2.inf' hX2ne (fun z => G.dist b z) = 2 := by exact_mod_cast hcast have hzdist : G.dist b z = 2 := by rw [← hzeq, hdseq] obtain ⟨p, hp⟩ := hG.exists_walk_length_eq_dist b z have hp2 : p.length = 2 := by rw [hp, hzdist] refine ⟨p.getVert 1, ?_, ?_⟩ · have := p.adj_getVert_succ (i := 0) (by rw [hp2]; omega); simpa using this · have hzX := (hX2sub z hzmem).2 have hadj : G.Adj (p.getVert 1) z := by have h := p.adj_getVert_succ (i := 1) (by rw [hp2]; omega) have h2' : p.getVert 2 = z := by rw [← hp2]; exact p.getVert_length rwa [h2'] at h exact hzX _ hadj.symm let φ : V → Sym2 V := fun b => if h : ∃ c : V, G.Adj b c ∧ c ∈ X then s(h.choose, b) else s(b, b) apply Finset.card_le_card_of_injOn φ · intro b hb have hb' : b ∈ S2 := hb rw [hS2, Finset.mem_filter] at hb' obtain ⟨hbN, hfb⟩ := hb' have hbXc : b ∈ (Xᶜ : Finset V) := hyint b ((SimpleGraph.mem_neighborFinset G y b).mp hbN) rw [Finset.mem_compl] at hbXc have hh := hex b hb have hφb : φ b = s(hh.choose, b) := by simp only [φ]; exact dif_pos hh have hspec := hh.choose_spec rw [Finset.mem_coe, hC, Finset.mem_filter] refine ⟨?_, ?_⟩ · rw [hφb, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet]; exact hspec.1.symm · rw [hφb] exact ⟨hh.choose, hspec.2, b, by rw [Finset.mem_compl]; exact hbXc, rfl⟩ · intro b1 hb1 b2 hb2 heq have hb1' : b1 ∈ S2 := hb1 have hb2' : b2 ∈ S2 := hb2 rw [hS2, Finset.mem_filter] at hb1' hb2' obtain ⟨hb1N, _⟩ := hb1' obtain ⟨hb2N, _⟩ := hb2' have hb1Xc : b1 ∈ (Xᶜ : Finset V) := hyint b1 ((SimpleGraph.mem_neighborFinset G y b1).mp hb1N) have hb2Xc : b2 ∈ (Xᶜ : Finset V) := hyint b2 ((SimpleGraph.mem_neighborFinset G y b2).mp hb2N) rw [Finset.mem_compl] at hb1Xc hb2Xc have hh1 := hex b1 hb1 have hh2 := hex b2 hb2 have hφ1 : φ b1 = s(hh1.choose, b1) := by simp only [φ]; exact dif_pos hh1 have hφ2 : φ b2 = s(hh2.choose, b2) := by simp only [φ]; exact dif_pos hh2 rw [hφ1, hφ2] at heq by_contra hne rw [Sym2.eq_iff] at heq rcases heq with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact hne h2 · exact hb1Xc (h2 ▸ hh2.choose_spec.2)
$|S_1| \le |C|$.
For each $b \in S_1$, $b \in N(x)$ implies $b \in X$ (since $x \in X_2$), but $b \notin X_2$, so $b$ has some neighbor $w \in X^c$. Then $\{b, w\} \in C$. Mapping each $b \in S_1$ to $\{b, w\}$ gives an injection into $C$ because $b$ is the unique endpoint lying in $X$, hence $|S_1| \le |C|$.
uses
Finset.mem_filter,SimpleGraph.mem_neighborFinset,Finset.card_le_card_of_injOn,dif_pos,Finset.mem_coe,SimpleGraph.mem_edgeFinset,SimpleGraph.mem_edgeSet,Finset.mem_compl,Sym2.eq_iffhave hS1k : S1.card ≤ C.card := by have hex : ∀ b ∈ S1, ∃ w : V, G.Adj b w ∧ w ∉ X := by intro b hb rw [hS1, Finset.mem_filter] at hb obtain ⟨hbN, hbX2⟩ := hb have hbX : b ∈ X := hxint b ((SimpleGraph.mem_neighborFinset G x b).mp hbN) by_contra h push Not at h exact hbX2 (by rw [hX2def, Finset.mem_filter]; exact ⟨hbX, h⟩) let φ : V → Sym2 V := fun b => if h : ∃ w : V, G.Adj b w ∧ w ∉ X then s(b, h.choose) else s(b, b) apply Finset.card_le_card_of_injOn φ · intro b hb have hb' : b ∈ S1 := hb rw [hS1, Finset.mem_filter] at hb' obtain ⟨hbN, hbX2⟩ := hb' have hbX : b ∈ X := hxint b ((SimpleGraph.mem_neighborFinset G x b).mp hbN) have hh := hex b hb have hφb : φ b = s(b, hh.choose) := by simp only [φ]; exact dif_pos hh have hspec := hh.choose_spec rw [Finset.mem_coe, hC, Finset.mem_filter] refine ⟨?_, ?_⟩ · rw [hφb, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet]; exact hspec.1 · rw [hφb] exact ⟨b, hbX, hh.choose, by rw [Finset.mem_compl]; exact hspec.2, rfl⟩ · intro b1 hb1 b2 hb2 heq have hb1' : b1 ∈ S1 := hb1 rw [hS1, Finset.mem_filter] at hb1' obtain ⟨hb1N, _⟩ := hb1' have hb1X : b1 ∈ X := hxint b1 ((SimpleGraph.mem_neighborFinset G x b1).mp hb1N) have hh1 := hex b1 hb1 have hh2 := hex b2 hb2 have hφ1 : φ b1 = s(b1, hh1.choose) := by simp only [φ]; exact dif_pos hh1 have hφ2 : φ b2 = s(b2, hh2.choose) := by simp only [φ]; exact dif_pos hh2 rw [hφ1, hφ2] at heq by_contra hne rw [Sym2.eq_iff] at heq rcases heq with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact hne h1 · exact hh2.choose_spec.2 (h1 ▸ hb1X)
$\sum_{a \in N(x)} f(a) = |S_1|$.
For $a \in N(x)$, $f(a) \le \operatorname{dist}(a, x) = 1$. If $a \in X_2$, $f(a) = 0$. If $a \notin X_2$, $a$ is not in $X_2$ so its distance to any vertex in $X_2$ is at least 1, giving $f(a) = 1$. Thus $f(a) = 1$ exactly when $a \in S_1$, and summing over all neighbors of $x$ gives $|S_1|$.
uses
SimpleGraph.mem_neighborFinset,SimpleGraph.dist_comm,SimpleGraph.dist_eq_one_iff_adj,Finset.inf'_le,SimpleGraph.dist_self,Nat.zero_le,le_antisymm,if_neg,SimpleGraph.dist_ne_zero_iff_ne_and_reachable,Finset.le_inf',if_pos,Finset.sum_congr,Finset.sum_boolehave hAxfull : (∑ a ∈ G.neighborFinset x, f a) = (S1.card : ℝ) := by have hterm : ∀ a ∈ G.neighborFinset x, f a = (if a ∉ X2 then (1:ℝ) else 0) := by intro a ha have hax : G.Adj x a := (SimpleGraph.mem_neighborFinset G x a).mp ha have hdx : G.dist a x = 1 := by rw [SimpleGraph.dist_comm]; exact SimpleGraph.dist_eq_one_iff_adj.mpr hax have hfle : f a ≤ 1 := by rw [hfval] have h1 : X2.inf' hX2ne (fun z => G.dist a z) ≤ G.dist a x := Finset.inf'_le _ hxX2 rw [hdx] at h1 have h2 : ((X2.inf' hX2ne (fun z => G.dist a z) : ℕ) : ℝ) ≤ 1 := by exact_mod_cast h1 linarith by_cases h : a ∈ X2 · have hz : f a = 0 := by rw [hfval] have h1 : X2.inf' hX2ne (fun z => G.dist a z) ≤ G.dist a a := Finset.inf'_le _ h rw [SimpleGraph.dist_self] at h1 have h2 : (0:ℕ) ≤ X2.inf' hX2ne (fun z => G.dist a z) := Nat.zero_le _ have hinf : X2.inf' hX2ne (fun z => G.dist a z) = 0 := le_antisymm h1 h2 rw [hinf]; norm_num rw [hz, if_neg (by simp [h])] · have hge1 : 1 ≤ f a := by rw [hfval] have hge' : ∀ z ∈ X2, 1 ≤ G.dist a z := by intro z hz have haz : a ≠ z := by intro hh; exact h (hh ▸ hz) have hne : G.dist a z ≠ 0 := by rw [SimpleGraph.dist_ne_zero_iff_ne_and_reachable] exact ⟨haz, hG a z⟩ omega have := Finset.le_inf' hX2ne (fun z => G.dist a z) hge' exact_mod_cast this rw [if_pos h]; linarith rw [Finset.sum_congr rfl hterm, Finset.sum_boole, hS1]
$\sum_{b \in N(y)} (3 - f(b)) \le |S_2|$.
For $b \in N(y)$, $f(b)$ is an integer $\ge 2$. If $f(b) = 2$, then $3 - f(b) = 1$. If $f(b) \ne 2$, then $f(b) \ge 3$, so $3 - f(b) \le 0$. Thus $3 - f(b) \le 1_{f(b) = 2}$ for all $b \in N(y)$, and summing over $N(y)$ yields $\le |S_2|$.
uses
lt_of_le_of_ne,Finset.sum_le_sum,Finset.sum_boolehave hAyfull : (∑ b ∈ G.neighborFinset y, (3 - f b)) ≤ (S2.card : ℝ) := by have hterm : ∀ b ∈ G.neighborFinset y, (3 - f b) ≤ (if f b = 2 then (1:ℝ) else 0) := by intro b hb have h2 := h2le b hb obtain ⟨m, hm⟩ : ∃ m : ℕ, f b = (m:ℝ) := ⟨_, hfval b⟩ rw [hm] at h2 ⊢ split_ifs with h · linarith · have hne : (2:ℝ) ≠ (m:ℝ) := fun hh => h hh.symm have hgt : (2:ℝ) < (m:ℝ) := lt_of_le_of_ne h2 hne have hgtm : 2 < m := by exact_mod_cast hgt have h3m : (3:ℝ) ≤ (m:ℝ) := by exact_mod_cast (by omega : 3 ≤ m) linarith calc (∑ b ∈ G.neighborFinset y, (3 - f b)) ≤ ∑ b ∈ G.neighborFinset y, (if f b = 2 then (1:ℝ) else 0) := Finset.sum_le_sum hterm _ = (S2.card : ℝ) := by rw [Finset.sum_boole, hS2]
Applying the potential bound yields $\kappa_{\mathrm{LLY}}(y, x) \le \frac{1}{3}\left( \frac{|S_2|}{\deg y} + \frac{|S_1|}{\deg x} \right)$.
Since $f$ is 1-Lipschitz and $f(y) - f(x) = 3 = \operatorname{dist}(y, x)$, `graph_lly_curvature_le_of_lipschitz_cut_potential` bounds $\kappa_{\mathrm{LLY}}(y, x)$ by $\frac{1}{3}\left( 3 - \frac{1}{\deg y}\sum_{b \in N(y)} f(b) + \frac{1}{\deg x}\sum_{a \in N(x)} f(a) \right)$. We rewrite $3 - \frac{1}{\deg y}\sum f(b) = \frac{1}{\deg y}\sum (3 - f(b)) \le \frac{|S_2|}{\deg y}$, while the $x$-sum evaluates to $\frac{|S_1|}{\deg x}$.
uses
SimpleGraph.dist_comm,graph_lly_curvature_le_of_lipschitz_cut_potential,SimpleGraph.Preconnected.minDegree_pos_of_nontrivial,lt_of_lt_of_le,Finset.sum_sub_distrib,Finset.sum_const,SimpleGraph.card_neighborFinset_eq_degree,nsmul_eq_mul,div_le_div_iff_of_pos_righthave hval : f y - f x = (G.dist y x : ℝ) := by rw [hfy, hfx, SimpleGraph.dist_comm, hd3]; norm_num have hpot := graph_lly_curvature_le_of_lipschitz_cut_potential G hG y x hxy.symm f hf hval have hdist : (G.dist y x : ℝ) = 3 := by rw [SimpleGraph.dist_comm, hd3]; norm_num rw [hdist] at hpot haveI : Nontrivial V := ⟨⟨x, y, hxy⟩⟩ have hδ0 : 0 < G.minDegree := SimpleGraph.Preconnected.minDegree_pos_of_nontrivial hG.preconnected have hδR : (0:ℝ) < (G.minDegree : ℝ) := by exact_mod_cast hδ0 have hdyδ : (G.minDegree : ℝ) ≤ (G.degree y : ℝ) := by exact_mod_cast G.minDegree_le_degree y have hdxδ : (G.minDegree : ℝ) ≤ (G.degree x : ℝ) := by exact_mod_cast G.minDegree_le_degree x have hdy : (0:ℝ) < (G.degree y : ℝ) := lt_of_lt_of_le hδR hdyδ have hdx : (0:ℝ) < (G.degree x : ℝ) := lt_of_lt_of_le hδR hdxδ have hAy : 3 - (∑ b ∈ G.neighborFinset y, f b) / (G.degree y : ℝ) ≤ (S2.card : ℝ) / (G.degree y : ℝ) := by have he : 3 - (∑ b ∈ G.neighborFinset y, f b) / (G.degree y : ℝ) = (∑ b ∈ G.neighborFinset y, (3 - f b)) / (G.degree y : ℝ) := by rw [Finset.sum_sub_distrib, Finset.sum_const, SimpleGraph.card_neighborFinset_eq_degree, nsmul_eq_mul] field_simp rw [he, div_le_div_iff_of_pos_right hdy] exact hAyfull have hAx : (∑ b ∈ G.neighborFinset x, f b) / (G.degree x : ℝ) ≤ (S1.card : ℝ) / (G.degree x : ℝ) := by rw [hAxfull] have hk : (S2.card : ℝ) ≤ (C.card : ℝ) := by exact_mod_cast hS2k have hk1 : (S1.card : ℝ) ≤ (C.card : ℝ) := by exact_mod_cast hS1k
$\kappa_{\mathrm{LLY}}(x, y) \le \frac{2|C|}{3 \delta(G)}$.
Using $|S_2| \le |C|$ and $\deg y \ge \delta(G)$, we have $\frac{|S_2|}{\deg y} \le \frac{|C|}{\delta(G)}$, and similarly $\frac{|S_1|}{\deg x} \le \frac{|C|}{\delta(G)}$. Adding these gives $\le \frac{2|C|}{\delta(G)}$. Since $\kappa_{\mathrm{LLY}}(x, y) = \kappa_{\mathrm{LLY}}(y, x)$ by symmetry, dividing by 3 concludes the proof.
uses
graph_lly_curvature_comm,le_trans,div_le_div_iff_of_pos_righthave harr : (S2.card : ℝ) / (G.degree y : ℝ) + (S1.card : ℝ) / (G.degree x : ℝ) ≤ 2 * (C.card : ℝ) / (G.minDegree : ℝ) := by have h1 : (S2.card : ℝ) / (G.degree y : ℝ) ≤ (C.card : ℝ) / (G.minDegree : ℝ) := by calc (S2.card : ℝ) / (G.degree y : ℝ) ≤ (S2.card : ℝ) / (G.minDegree : ℝ) := by gcongr _ ≤ (C.card : ℝ) / (G.minDegree : ℝ) := by gcongr have h2 : (S1.card : ℝ) / (G.degree x : ℝ) ≤ (C.card : ℝ) / (G.minDegree : ℝ) := by calc (S1.card : ℝ) / (G.degree x : ℝ) ≤ (S1.card : ℝ) / (G.minDegree : ℝ) := by gcongr _ ≤ (C.card : ℝ) / (G.minDegree : ℝ) := by gcongr calc (S2.card : ℝ) / (G.degree y : ℝ) + (S1.card : ℝ) / (G.degree x : ℝ) ≤ (C.card : ℝ) / (G.minDegree : ℝ) + (C.card : ℝ) / (G.minDegree : ℝ) := by linarith _ = 2 * (C.card : ℝ) / (G.minDegree : ℝ) := by ring rw [graph_lly_curvature_comm] have e2 : 2 * (C.card : ℝ) / (3 * (G.minDegree : ℝ)) = (2 * (C.card : ℝ) / (G.minDegree : ℝ)) / 3 := by field_simp rw [e2] refine le_trans hpot ?_ rw [div_le_div_iff_of_pos_right (by norm_num : (0:ℝ) < 3)] linarith
Finset.mem_filter- An element belongs to `Finset.filter p s` if and only if it belongs to `s` and satisfies the predicate `p`.
SimpleGraph.dist_self- The graph distance from any vertex to itself is zero.
Finset.inf'_le- The infimum of a function over a nonempty finite set is bounded above by the function value at any element of the set.
Nat.zero_le- Every natural number is greater than or equal to zero.
le_antisymm- If $a \le b$ and $b \le a$, then $a = b$.
Finset.mem_compl- An element belongs to the complement of a finite set $s$ if and only if it does not belong to $s$.
SimpleGraph.dist_ne_zero_iff_ne_and_reachable- The distance between two vertices is nonzero if and only if they are distinct and there is a path between them.
SimpleGraph.dist_eq_one_iff_adj- The distance between two vertices is 1 if and only if they are adjacent.
SimpleGraph.dist_comm- Graph distance is symmetric: $d(u, v) = d(v, u)$.
Finset.le_inf'- If a value $a$ is bounded above by $f(b)$ for every element $b$ in a nonempty finite set, then $a \le \inf' f$.
Finset.exists_mem_eq_inf'- On any nonempty finite set, the infimum of a linearly ordered function is achieved at some element of the set.
SimpleGraph.Reachable.dist_triangle_left- The triangle inequality for graph distance: $d(u, w) \le d(u, v) + d(v, w)$ when $v$ is reachable from $u$.
Nat.cast_le- An inequality $m \le n$ between natural numbers is equivalent to the corresponding inequality between their real casts.
Nat.cast_add- The cast of the sum of two natural numbers equals the sum of their casts.
SimpleGraph.mem_neighborFinset- A vertex $w$ is in the neighbor finset of $v$ if and only if $v$ and $w$ are adjacent in the graph.
Finset.card_le_card_of_injOn- If a map from a finite set $s$ to a finite set $t$ is injective on $s$, then $|s| \le |t|$.
dif_pos- A dependent if-then-else evaluates to the then-branch when the condition is true.
Finset.mem_coe- Membership in a coerced finset is equivalent to membership in the finset.
SimpleGraph.mem_edgeFinset- An unordered pair belongs to the edge finset of a graph if and only if it belongs to the edge set.
SimpleGraph.mem_edgeSet- An unordered pair $s(v, w)$ belongs to the edge set if and only if $v$ and $w$ are adjacent.
Sym2.eq_iff- Two unordered pairs $\{x, y\}$ and $\{z, w\}$ are equal if and only if $(x = z \land y = w)$ or $(x = w \land y = z)$.
if_neg- An if-then-else expression evaluates to the else-branch when the condition is false.
if_pos- An if-then-else expression evaluates to the then-branch when the condition is true.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree on all elements.
Finset.sum_boole- The sum over a finite set of the indicator of a predicate equals the cardinality of the subset satisfying the predicate.
lt_of_le_of_ne- If $a \le b$ and $a \ne b$, then $a < b$.
Finset.sum_le_sum- If $f(i) \le g(i)$ for all elements $i$ in a finite set, then $\sum_i f(i) \le \sum_i g(i)$.
graph_lly_curvature_le_of_lipschitz_cut_potential- If $f$ is a 1-Lipschitz function satisfying $f(x) - f(y) = d(x, y)$, then $\kappa_{\mathrm{LLY}}(x, y) \le \frac{1}{d(x,y)}\left( d(x,y) - \frac{1}{\deg x}\sum_{a \sim x} f(a) + \frac{1}{\deg y}\sum_{b \sim y} f(b) \right)$.
SimpleGraph.Preconnected.minDegree_pos_of_nontrivial- A preconnected graph on a nontrivial finite vertex type has strictly positive minimum degree.
lt_of_lt_of_le- If $a < b$ and $b \le c$, then $a < c$.
Finset.sum_sub_distrib- The sum of differences $\sum (f(x) - g(x))$ over a finite set equals $\sum f(x) - \sum g(x)$.
Finset.sum_const- The sum of a constant $b$ over a finite set $s$ equals $|s| \cdot b$.
SimpleGraph.card_neighborFinset_eq_degree- The number of neighbors of a vertex equals its degree.
nsmul_eq_mul- Natural scalar multiplication $n \cdot a$ equals the product of $n$ cast into the semiring with $a$.
div_le_div_iff_of_pos_right- Dividing by a strictly positive number preserves the direction of an inequality.
graph_lly_curvature_comm- Lin–Lu–Yau curvature is symmetric: $\kappa_{\mathrm{LLY}}(x, y) = \kappa_{\mathrm{LLY}}(y, x)$.
le_trans- If $a \le b$ and $b \le c$, then $a \le c$.
- The injections from $S_2$ and $S_1$ into the cut edge set $C = E(X, X^c)$ rely on classical choice to pick a specific crossing neighbor for each boundary vertex.
- The potential bound lemma `graph_lly_curvature_le_of_lipschitz_cut_potential` is applied with the roles of $x$ and $y$ swapped because $f(y) - f(x) = d(y, x) = 3$; the bound on $\kappa_{\mathrm{LLY}}(x, y)$ is then deduced using the symmetry lemma `graph_lly_curvature_comm`.
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.
/-- Interior-pair case of the cut bound on κ_LLY at distance 3. -/theorem exists_dist_three_lly_curvature_le_cut_interior {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (X : Finset V) (x y : V) (hxX : x ∈ X) (hxint : ∀ w : V, G.Adj x w → w ∈ X) (hyX : y ∈ (Xᶜ : Finset V)) (hyint : ∀ w : V, G.Adj y w → w ∈ (Xᶜ : Finset V)) (hd3 : G.dist x y = 3) : graph_lly_curvature G x y ≤ (2 * ((G.edgeFinset.filter (fun e => ∃ u ∈ X, ∃ v ∈ (Xᶜ : Finset V), e = s(u, v))).card : ℝ)) / (3 * (G.minDegree : ℝ)) := by classical set X2 : Finset V := X.filter (fun z => ∀ w : V, G.Adj z w → w ∈ X) with hX2def have hX2sub : ∀ z ∈ X2, z ∈ X ∧ ∀ w : V, G.Adj z w → w ∈ X := by intro z hz; rw [hX2def, Finset.mem_filter] at hz; exact hz have hxX2 : x ∈ X2 := by rw [hX2def, Finset.mem_filter]; exact ⟨hxX, hxint⟩ have hX2ne : X2.Nonempty := ⟨x, hxX2⟩ let f : V → ℝ := fun v => ((X2.inf' hX2ne (fun z => G.dist v z) : ℕ) : ℝ) have hfval : ∀ v : V, f v = ((X2.inf' hX2ne (fun z => G.dist v z) : ℕ) : ℝ) := fun v => rfl set C : Finset (Sym2 V) := G.edgeFinset.filter (fun e => ∃ u ∈ X, ∃ v ∈ (Xᶜ : Finset V), e = s(u, v)) with hC set S2 : Finset V := (G.neighborFinset y).filter (fun b => f b = 2) with hS2 set S1 : Finset V := (G.neighborFinset x).filter (fun a => a ∉ X2) with hS1 have hxy : x ≠ y := by intro h; rw [h, SimpleGraph.dist_self] at hd3; omega have hfx : f x = 0 := by have h1 : X2.inf' hX2ne (fun z => G.dist x z) ≤ G.dist x x := Finset.inf'_le _ hxX2 rw [SimpleGraph.dist_self] at h1 have h2 : (0:ℕ) ≤ X2.inf' hX2ne (fun z => G.dist x z) := Nat.zero_le _ have hinf : X2.inf' hX2ne (fun z => G.dist x z) = 0 := le_antisymm h1 h2 rw [hfval, hinf]; norm_num have hge : ∀ z ∈ X2, 3 ≤ G.dist y z := by intro z hz obtain ⟨hzX, hzint⟩ := hX2sub z hz by_contra hlt push Not at hlt have hzy : z ≠ y := by intro h; rw [h] at hzX; rw [Finset.mem_compl] at hyX; exact hyX hzX have hyz_ne : G.dist y z ≠ 0 := by rw [SimpleGraph.dist_ne_zero_iff_ne_and_reachable] exact ⟨fun h => hzy h.symm, hG y z⟩ have : G.dist y z = 1 ∨ G.dist y z = 2 := by omega rcases this with h1 | h2 · have hadj : G.Adj y z := by rw [← SimpleGraph.dist_eq_one_iff_adj, h1] have hzc : z ∈ (Xᶜ : Finset V) := hyint z hadj rw [Finset.mem_compl] at hzc; exact hzc hzX · obtain ⟨p, hp⟩ := hG.exists_walk_length_eq_dist y z have hp2 : p.length = 2 := by rw [hp, h2] have hadjyc : G.Adj y (p.getVert 1) := by have := p.adj_getVert_succ (i := 0) (by rw [hp2]; omega); simpa using this have hadjcz : G.Adj z (p.getVert 1) := by have h := p.adj_getVert_succ (i := 1) (by rw [hp2]; omega) have h2' : p.getVert 2 = z := by rw [← hp2]; exact p.getVert_length rw [h2'] at h; exact h.symm have hcXc : p.getVert 1 ∈ (Xᶜ : Finset V) := hyint _ hadjyc rw [Finset.mem_compl] at hcXc exact hcXc (hzint _ hadjcz) have hfy : f y = 3 := by have hle : X2.inf' hX2ne (fun z => G.dist y z) ≤ 3 := by have := Finset.inf'_le (fun z => G.dist y z) hxX2 rwa [SimpleGraph.dist_comm, hd3] at this have hge' : 3 ≤ X2.inf' hX2ne (fun z => G.dist y z) := Finset.le_inf' hX2ne _ hge have hinf : X2.inf' hX2ne (fun z => G.dist y z) = 3 := le_antisymm hle hge' rw [hfval, hinf]; norm_num have hf : ∀ a b : V, f a - f b ≤ (G.dist a b : ℝ) := by intro a b obtain ⟨z0, hz0mem, hz0eq⟩ := Finset.exists_mem_eq_inf' hX2ne (fun z => G.dist b z) have h1 : X2.inf' hX2ne (fun z => G.dist a z) ≤ G.dist a z0 := Finset.inf'_le _ hz0mem have h2 : G.dist a z0 ≤ G.dist a b + G.dist b z0 := SimpleGraph.Reachable.dist_triangle_left (hG a b) z0 have hds : X2.inf' hX2ne (fun z => G.dist a z) ≤ X2.inf' hX2ne (fun z => G.dist b z) + G.dist a b := by rw [hz0eq]; omega have hcast : ((X2.inf' hX2ne (fun z => G.dist a z) : ℕ) : ℝ) ≤ ((X2.inf' hX2ne (fun z => G.dist b z) : ℕ) : ℝ) + (G.dist a b : ℝ) := by have hc := (Nat.cast_le (α := ℝ)).mpr hds; rw [Nat.cast_add] at hc; exact hc rw [hfval, hfval] linarith have h2le : ∀ b ∈ G.neighborFinset y, (2:ℝ) ≤ f b := by intro b hb have hyb : G.Adj y b := (SimpleGraph.mem_neighborFinset G y b).mp hb have hbXc : b ∉ X := by have := hyint b hyb; rwa [Finset.mem_compl] at this have hge2 : ∀ z ∈ X2, 2 ≤ G.dist b z := by intro z hz obtain ⟨hzX, hzint⟩ := hX2sub z hz have hbz : b ≠ z := by intro h; exact hbXc (h ▸ hzX) have hne0 : G.dist b z ≠ 0 := by rw [SimpleGraph.dist_ne_zero_iff_ne_and_reachable] exact ⟨hbz, hG b z⟩ have hne1 : G.dist b z ≠ 1 := by intro h have hzb : G.dist z b = 1 := by rw [SimpleGraph.dist_comm]; exact h exact hbXc (hzint b (SimpleGraph.dist_eq_one_iff_adj.mp hzb)) omega have := Finset.le_inf' hX2ne (fun z => G.dist b z) hge2 rw [hfval] exact_mod_cast this have hS2k : S2.card ≤ C.card := by have hex : ∀ b ∈ S2, ∃ c : V, G.Adj b c ∧ c ∈ X := by intro b hb rw [hS2, Finset.mem_filter] at hb obtain ⟨hbN, hfb⟩ := hb obtain ⟨z, hzmem, hzeq⟩ := Finset.exists_mem_eq_inf' hX2ne (fun z => G.dist b z) have hcast : ((X2.inf' hX2ne (fun z => G.dist b z) : ℕ) : ℝ) = 2 := by rw [← hfval b]; exact hfb have hdseq : X2.inf' hX2ne (fun z => G.dist b z) = 2 := by exact_mod_cast hcast have hzdist : G.dist b z = 2 := by rw [← hzeq, hdseq] obtain ⟨p, hp⟩ := hG.exists_walk_length_eq_dist b z have hp2 : p.length = 2 := by rw [hp, hzdist] refine ⟨p.getVert 1, ?_, ?_⟩ · have := p.adj_getVert_succ (i := 0) (by rw [hp2]; omega); simpa using this · have hzX := (hX2sub z hzmem).2 have hadj : G.Adj (p.getVert 1) z := by have h := p.adj_getVert_succ (i := 1) (by rw [hp2]; omega) have h2' : p.getVert 2 = z := by rw [← hp2]; exact p.getVert_length rwa [h2'] at h exact hzX _ hadj.symm let φ : V → Sym2 V := fun b => if h : ∃ c : V, G.Adj b c ∧ c ∈ X then s(h.choose, b) else s(b, b) apply Finset.card_le_card_of_injOn φ · intro b hb have hb' : b ∈ S2 := hb rw [hS2, Finset.mem_filter] at hb' obtain ⟨hbN, hfb⟩ := hb' have hbXc : b ∈ (Xᶜ : Finset V) := hyint b ((SimpleGraph.mem_neighborFinset G y b).mp hbN) rw [Finset.mem_compl] at hbXc have hh := hex b hb have hφb : φ b = s(hh.choose, b) := by simp only [φ]; exact dif_pos hh have hspec := hh.choose_spec rw [Finset.mem_coe, hC, Finset.mem_filter] refine ⟨?_, ?_⟩ · rw [hφb, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet]; exact hspec.1.symm · rw [hφb] exact ⟨hh.choose, hspec.2, b, by rw [Finset.mem_compl]; exact hbXc, rfl⟩ · intro b1 hb1 b2 hb2 heq have hb1' : b1 ∈ S2 := hb1 have hb2' : b2 ∈ S2 := hb2 rw [hS2, Finset.mem_filter] at hb1' hb2' obtain ⟨hb1N, _⟩ := hb1' obtain ⟨hb2N, _⟩ := hb2' have hb1Xc : b1 ∈ (Xᶜ : Finset V) := hyint b1 ((SimpleGraph.mem_neighborFinset G y b1).mp hb1N) have hb2Xc : b2 ∈ (Xᶜ : Finset V) := hyint b2 ((SimpleGraph.mem_neighborFinset G y b2).mp hb2N) rw [Finset.mem_compl] at hb1Xc hb2Xc have hh1 := hex b1 hb1 have hh2 := hex b2 hb2 have hφ1 : φ b1 = s(hh1.choose, b1) := by simp only [φ]; exact dif_pos hh1 have hφ2 : φ b2 = s(hh2.choose, b2) := by simp only [φ]; exact dif_pos hh2 rw [hφ1, hφ2] at heq by_contra hne rw [Sym2.eq_iff] at heq rcases heq with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact hne h2 · exact hb1Xc (h2 ▸ hh2.choose_spec.2) have hS1k : S1.card ≤ C.card := by have hex : ∀ b ∈ S1, ∃ w : V, G.Adj b w ∧ w ∉ X := by intro b hb rw [hS1, Finset.mem_filter] at hb obtain ⟨hbN, hbX2⟩ := hb have hbX : b ∈ X := hxint b ((SimpleGraph.mem_neighborFinset G x b).mp hbN) by_contra h push Not at h exact hbX2 (by rw [hX2def, Finset.mem_filter]; exact ⟨hbX, h⟩) let φ : V → Sym2 V := fun b => if h : ∃ w : V, G.Adj b w ∧ w ∉ X then s(b, h.choose) else s(b, b) apply Finset.card_le_card_of_injOn φ · intro b hb have hb' : b ∈ S1 := hb rw [hS1, Finset.mem_filter] at hb' obtain ⟨hbN, hbX2⟩ := hb' have hbX : b ∈ X := hxint b ((SimpleGraph.mem_neighborFinset G x b).mp hbN) have hh := hex b hb have hφb : φ b = s(b, hh.choose) := by simp only [φ]; exact dif_pos hh have hspec := hh.choose_spec rw [Finset.mem_coe, hC, Finset.mem_filter] refine ⟨?_, ?_⟩ · rw [hφb, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet]; exact hspec.1 · rw [hφb] exact ⟨b, hbX, hh.choose, by rw [Finset.mem_compl]; exact hspec.2, rfl⟩ · intro b1 hb1 b2 hb2 heq have hb1' : b1 ∈ S1 := hb1 rw [hS1, Finset.mem_filter] at hb1' obtain ⟨hb1N, _⟩ := hb1' have hb1X : b1 ∈ X := hxint b1 ((SimpleGraph.mem_neighborFinset G x b1).mp hb1N) have hh1 := hex b1 hb1 have hh2 := hex b2 hb2 have hφ1 : φ b1 = s(b1, hh1.choose) := by simp only [φ]; exact dif_pos hh1 have hφ2 : φ b2 = s(b2, hh2.choose) := by simp only [φ]; exact dif_pos hh2 rw [hφ1, hφ2] at heq by_contra hne rw [Sym2.eq_iff] at heq rcases heq with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact hne h1 · exact hh2.choose_spec.2 (h1 ▸ hb1X) have hAxfull : (∑ a ∈ G.neighborFinset x, f a) = (S1.card : ℝ) := by have hterm : ∀ a ∈ G.neighborFinset x, f a = (if a ∉ X2 then (1:ℝ) else 0) := by intro a ha have hax : G.Adj x a := (SimpleGraph.mem_neighborFinset G x a).mp ha have hdx : G.dist a x = 1 := by rw [SimpleGraph.dist_comm]; exact SimpleGraph.dist_eq_one_iff_adj.mpr hax have hfle : f a ≤ 1 := by rw [hfval] have h1 : X2.inf' hX2ne (fun z => G.dist a z) ≤ G.dist a x := Finset.inf'_le _ hxX2 rw [hdx] at h1 have h2 : ((X2.inf' hX2ne (fun z => G.dist a z) : ℕ) : ℝ) ≤ 1 := by exact_mod_cast h1 linarith by_cases h : a ∈ X2 · have hz : f a = 0 := by rw [hfval] have h1 : X2.inf' hX2ne (fun z => G.dist a z) ≤ G.dist a a := Finset.inf'_le _ h rw [SimpleGraph.dist_self] at h1 have h2 : (0:ℕ) ≤ X2.inf' hX2ne (fun z => G.dist a z) := Nat.zero_le _ have hinf : X2.inf' hX2ne (fun z => G.dist a z) = 0 := le_antisymm h1 h2 rw [hinf]; norm_num rw [hz, if_neg (by simp [h])] · have hge1 : 1 ≤ f a := by rw [hfval] have hge' : ∀ z ∈ X2, 1 ≤ G.dist a z := by intro z hz have haz : a ≠ z := by intro hh; exact h (hh ▸ hz) have hne : G.dist a z ≠ 0 := by rw [SimpleGraph.dist_ne_zero_iff_ne_and_reachable] exact ⟨haz, hG a z⟩ omega have := Finset.le_inf' hX2ne (fun z => G.dist a z) hge' exact_mod_cast this rw [if_pos h]; linarith rw [Finset.sum_congr rfl hterm, Finset.sum_boole, hS1] have hAyfull : (∑ b ∈ G.neighborFinset y, (3 - f b)) ≤ (S2.card : ℝ) := by have hterm : ∀ b ∈ G.neighborFinset y, (3 - f b) ≤ (if f b = 2 then (1:ℝ) else 0) := by intro b hb have h2 := h2le b hb obtain ⟨m, hm⟩ : ∃ m : ℕ, f b = (m:ℝ) := ⟨_, hfval b⟩ rw [hm] at h2 ⊢ split_ifs with h · linarith · have hne : (2:ℝ) ≠ (m:ℝ) := fun hh => h hh.symm have hgt : (2:ℝ) < (m:ℝ) := lt_of_le_of_ne h2 hne have hgtm : 2 < m := by exact_mod_cast hgt have h3m : (3:ℝ) ≤ (m:ℝ) := by exact_mod_cast (by omega : 3 ≤ m) linarith calc (∑ b ∈ G.neighborFinset y, (3 - f b)) ≤ ∑ b ∈ G.neighborFinset y, (if f b = 2 then (1:ℝ) else 0) := Finset.sum_le_sum hterm _ = (S2.card : ℝ) := by rw [Finset.sum_boole, hS2] have hval : f y - f x = (G.dist y x : ℝ) := by rw [hfy, hfx, SimpleGraph.dist_comm, hd3]; norm_num have hpot := graph_lly_curvature_le_of_lipschitz_cut_potential G hG y x hxy.symm f hf hval have hdist : (G.dist y x : ℝ) = 3 := by rw [SimpleGraph.dist_comm, hd3]; norm_num rw [hdist] at hpot haveI : Nontrivial V := ⟨⟨x, y, hxy⟩⟩ have hδ0 : 0 < G.minDegree := SimpleGraph.Preconnected.minDegree_pos_of_nontrivial hG.preconnected have hδR : (0:ℝ) < (G.minDegree : ℝ) := by exact_mod_cast hδ0 have hdyδ : (G.minDegree : ℝ) ≤ (G.degree y : ℝ) := by exact_mod_cast G.minDegree_le_degree y have hdxδ : (G.minDegree : ℝ) ≤ (G.degree x : ℝ) := by exact_mod_cast G.minDegree_le_degree x have hdy : (0:ℝ) < (G.degree y : ℝ) := lt_of_lt_of_le hδR hdyδ have hdx : (0:ℝ) < (G.degree x : ℝ) := lt_of_lt_of_le hδR hdxδ have hAy : 3 - (∑ b ∈ G.neighborFinset y, f b) / (G.degree y : ℝ) ≤ (S2.card : ℝ) / (G.degree y : ℝ) := by have he : 3 - (∑ b ∈ G.neighborFinset y, f b) / (G.degree y : ℝ) = (∑ b ∈ G.neighborFinset y, (3 - f b)) / (G.degree y : ℝ) := by rw [Finset.sum_sub_distrib, Finset.sum_const, SimpleGraph.card_neighborFinset_eq_degree, nsmul_eq_mul] field_simp rw [he, div_le_div_iff_of_pos_right hdy] exact hAyfull have hAx : (∑ b ∈ G.neighborFinset x, f b) / (G.degree x : ℝ) ≤ (S1.card : ℝ) / (G.degree x : ℝ) := by rw [hAxfull] have hk : (S2.card : ℝ) ≤ (C.card : ℝ) := by exact_mod_cast hS2k have hk1 : (S1.card : ℝ) ≤ (C.card : ℝ) := by exact_mod_cast hS1k have harr : (S2.card : ℝ) / (G.degree y : ℝ) + (S1.card : ℝ) / (G.degree x : ℝ) ≤ 2 * (C.card : ℝ) / (G.minDegree : ℝ) := by have h1 : (S2.card : ℝ) / (G.degree y : ℝ) ≤ (C.card : ℝ) / (G.minDegree : ℝ) := by calc (S2.card : ℝ) / (G.degree y : ℝ) ≤ (S2.card : ℝ) / (G.minDegree : ℝ) := by gcongr _ ≤ (C.card : ℝ) / (G.minDegree : ℝ) := by gcongr have h2 : (S1.card : ℝ) / (G.degree x : ℝ) ≤ (C.card : ℝ) / (G.minDegree : ℝ) := by calc (S1.card : ℝ) / (G.degree x : ℝ) ≤ (S1.card : ℝ) / (G.minDegree : ℝ) := by gcongr _ ≤ (C.card : ℝ) / (G.minDegree : ℝ) := by gcongr calc (S2.card : ℝ) / (G.degree y : ℝ) + (S1.card : ℝ) / (G.degree x : ℝ) ≤ (C.card : ℝ) / (G.minDegree : ℝ) + (C.card : ℝ) / (G.minDegree : ℝ) := by linarith _ = 2 * (C.card : ℝ) / (G.minDegree : ℝ) := by ring rw [graph_lly_curvature_comm] have e2 : 2 * (C.card : ℝ) / (3 * (G.minDegree : ℝ)) = (2 * (C.card : ℝ) / (G.minDegree : ℝ)) / 3 := by field_simp rw [e2] refine le_trans hpot ?_ rw [div_le_div_iff_of_pos_right (by norm_num : (0:ℝ) < 3)] linarith