exists_cut_interior_pair_dist_three
If a cut (X, Xᶜ) has fewer edges than δ(G), then there exists a vertex x ∈ Xᶜ with no neighbours in X and a vertex y ∈ X with no neighbours in Xᶜ such that dist(x, y) = 3.
Statement
theorem exists_cut_interior_pair_dist_three {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (hd : 3 ≤ G.diam) (X : Finset V) (hX1 : X.Nonempty) (hX2 : (Xᶜ : Finset V).Nonempty) (hk : (G.edgeFinset.filter (fun e => ∃ u ∈ X, ∃ v ∈ (Xᶜ : Finset V), e = s(u, v))).card < G.minDegree) : ∃ (x y : V), G.dist x y = 3 ∧ x ∈ (Xᶜ : Finset V) ∧ (∀ u ∈ X, ¬ G.Adj x u) ∧ y ∈ X ∧ (∀ w ∈ (Xᶜ : Finset V), ¬ G.Adj y w)
- Source
- step towards exists_dist_three_cut_potential_witness
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
To prove that a cut (X, Xᶜ) with fewer edges than the minimum degree δ(G) contains an interior pair at distance 3, the proof first finds an edge ab crossing the cut. By constructing an injection from the neighbors of a into the cut edges, the degree bound |E(X, Xᶜ)| < δ(G) guarantees that a has a neighbor y ∈ X with no neighbors in Xᶜ, and symmetrically b has a neighbor x ∈ Xᶜ with no neighbors in X. The path y - a - b - x provides a walk of length 3, showing dist(x, y) ≤ 3. Finally, because x and y are in opposite sets and neither has neighbors in the opposite set, they cannot be equal, adjacent, or share any common neighbors, forcing dist(x, y) > 2 and hence dist(x, y) = 3.
By induction along the walk p, if no edge crosses from X to Xᶜ, every vertex of p remains in X.
We assume for contradiction that no edge connects a vertex in X to a vertex in Xᶜ. By induction on i, the vertex p.getVert i remains in X for all i ≤ p.length: the base case i = 0 holds because u ∈ X; for the inductive step, if p.getVert n ∈ X and p.getVert (n + 1) ∉ X, then p.getVert (n + 1) ∈ Xᶜ, so the walk step from p.getVert n to p.getVert (n + 1) provides a crossing edge, contradicting the assumption.
uses
Nat.le_of_succ_le,Finset.mem_complby_contra h push_neg at h have hstay : ∀ i ≤ p.length, p.getVert i ∈ X := by intro i induction i with | zero => intro _ simpa using hu | succ n ih => intro hn have hnX : p.getVert n ∈ X := ih (Nat.le_of_succ_le hn) by_contra hc have hcY : p.getVert (n + 1) ∈ (Xᶜ : Finset V) := by rw [Finset.mem_compl] exact hc exact h (p.getVert n) hnX (p.getVert (n + 1)) hcY (p.adj_getVert_succ hn)
Any walk from X to Xᶜ must contain a cut edge crossing between X and Xᶜ.
Evaluating the induction result at i = p.length shows that the terminal vertex p.getVert p.length must belong to X. But by assumption the walk terminates at v ∈ Xᶜ, yielding an immediate contradiction.
uses
le_rfl,SimpleGraph.Walk.getVert_length,Finset.mem_complhave hp : p.getVert p.length ∈ X := hstay p.length le_rfl have hvY : p.getVert p.length ∈ (Xᶜ : Finset V) := by simpa [SimpleGraph.Walk.getVert_length] using hv rw [Finset.mem_compl] at hvY exact hvY hp
In a connected graph, any cut (X, Xᶜ) between two non-empty sets has at least one crossing edge.
Pick a ∈ X and b ∈ Xᶜ. Since G is connected, there exists a walk p from a to b. Applying exists_cut_interior_pair_dist_three_aux_walk to p guarantees the existence of an edge crossing the cut.
uses
exists_cut_interior_pair_dist_three_aux_walkobtain ⟨a, ha⟩ := hX1 obtain ⟨b, hb⟩ := hX2 obtain ⟨p⟩ := hG.preconnected a b exact exists_cut_interior_pair_dist_three_aux_walk G X p ha hb
To show every u ∈ S has a neighbor in S with no neighbors in Sᶜ, we set up a proof by contradiction assuming every neighbor of u in S has a neighbor in Sᶜ.
We assume for contradiction that every neighbor y ∈ S of u has at least one neighbor in Sᶜ. We let C denote the set of cut edges between S and Sᶜ, whose cardinality is strictly less than δ(G).
classical by_contra hcon push_neg at hcon let C := G.edgeFinset.filter (fun e => ∃ a ∈ S, ∃ b ∈ (Sᶜ : Finset V), e = s(a, b)) change C.card < G.minDegree at hk
There is a map f assigning each neighbor of u to a cut edge in C.
For each neighbor y of u: if y ∈ S, the contradiction hypothesis gives a neighbor z ∈ Sᶜ of y, so we choose one and map y to the cut edge s(y, z) ∈ C; if y ∉ S (so y ∈ Sᶜ), the edge s(u, y) connects u ∈ S to y ∈ Sᶜ, so we map y to s(u, y) ∈ C.
uses
Classical.choose,Classical.choose_spec,Finset.mem_filter.mpr,Finset.mem_compllet f : ↥(G.neighborFinset u) → ↥C := fun y => if hy : (y : V) ∈ S then ⟨s((y : V), Classical.choose (hcon (y : V) hy ((G.mem_neighborFinset u (y : V)).mp y.2))), by obtain ⟨hzY, hzy⟩ := Classical.choose_spec (hcon (y : V) hy ((G.mem_neighborFinset u (y : V)).mp y.2)) refine Finset.mem_filter.mpr ⟨?_, ?_⟩ · exact (G.mem_edgeFinset).mpr ((G.mem_edgeSet).mpr hzy) · exact ⟨(y : V), hy, _, hzY, rfl⟩⟩ else ⟨s(u, (y : V)), by refine Finset.mem_filter.mpr ⟨?_, ?_⟩ · exact (G.mem_edgeFinset).mpr ((G.mem_edgeSet).mpr ((G.mem_neighborFinset u (y : V)).mp y.2)) · refine ⟨u, hu, (y : V), ?_, rfl⟩ rw [Finset.mem_compl] exact hy⟩
The map f from the neighbors of u to C is injective.
Assume f(y₁) = f(y₂). We split into four cases based on whether y₁, y₂ ∈ S: if both are in S, s(y₁, z₁) = s(y₂, z₂), which implies y₁ = y₂ since y₁ ∈ S cannot equal z₂ ∈ Sᶜ; if y₁ ∈ S and y₂ ∉ S, s(y₁, z₁) = s(u, y₂), which cannot hold because y₁ ≠ u (y₁ is adjacent to u) and y₁ ∈ S cannot equal y₂ ∉ S; the case y₁ ∉ S, y₂ ∈ S is symmetrically impossible; and if neither is in S, s(u, y₁) = s(u, y₂) forces y₁ = y₂. Thus f is injective in all cases.
uses
congrArg,Subtype.val,Sym2.eq_iff,Subtype.ext,Classical.choose,Classical.choose_spec,Finset.mem_complhave hinj : Function.Injective f := by intro y1 y2 h have hval : (f y1).1 = (f y2).1 := congrArg Subtype.val h simp only [f] at hval split_ifs at hval with hy1 hy2 hy2 hy1 · have adj1 : G.Adj u ↑y1 := (G.mem_neighborFinset u ↑y1).mp y1.2 have adj2 : G.Adj u ↑y2 := (G.mem_neighborFinset u ↑y2).mp y2.2 rw [Sym2.eq_iff] at hval obtain ⟨h1, h2⟩ | ⟨h1, h2⟩ := hval · exact Subtype.ext h1 · exfalso have hz2Y : Classical.choose (hcon ↑y2 hy2 adj2) ∈ (Sᶜ : Finset V) := (Classical.choose_spec (hcon ↑y2 hy2 adj2)).1 have hY : ↑y1 ∈ (Sᶜ : Finset V) := h1.symm ▸ hz2Y rw [Finset.mem_compl] at hY exact hY hy1 · exfalso have adj1 : G.Adj u ↑y1 := (G.mem_neighborFinset u ↑y1).mp y1.2 have adj2 : G.Adj u ↑y2 := (G.mem_neighborFinset u ↑y2).mp y2.2 have hz1Y : Classical.choose (hcon ↑y1 hy1 adj1) ∈ (Sᶜ : Finset V) := (Classical.choose_spec (hcon ↑y1 hy1 adj1)).1 rw [Sym2.eq_iff] at hval obtain ⟨h1, h2⟩ | ⟨h1, h2⟩ := hval · exact adj1.ne' h1 · exact hy2 (h1 ▸ hy1) · exfalso have adj1 : G.Adj u ↑y1 := (G.mem_neighborFinset u ↑y1).mp y1.2 have adj2 : G.Adj u ↑y2 := (G.mem_neighborFinset u ↑y2).mp y2.2 have hz2Y : Classical.choose (hcon ↑y2 hy2 adj2) ∈ (Sᶜ : Finset V) := (Classical.choose_spec (hcon ↑y2 hy2 adj2)).1 rw [Sym2.eq_iff] at hval obtain ⟨h1, h2⟩ | ⟨h1, h2⟩ := hval · exact adj2.ne h1 · rw [Finset.mem_compl] at hz2Y exact hz2Y (h1 ▸ hu) · have adj1 : G.Adj u ↑y1 := (G.mem_neighborFinset u ↑y1).mp y1.2 have adj2 : G.Adj u ↑y2 := (G.mem_neighborFinset u ↑y2).mp y2.2 rw [Sym2.eq_iff] at hval obtain ⟨h1, h2⟩ | ⟨h1, h2⟩ := hval · exact Subtype.ext h2 · exfalso exact hy1 (h2.symm ▸ hu)
The degree of u is strictly less than δ(G), which contradicts the definition of minimum degree.
Because f is injective, the number of neighbors deg(u) is at most |C|. Since |C| < δ(G) by hypothesis and δ(G) ≤ deg(u) for any vertex, we obtain δ(G) ≤ deg(u) ≤ |C| < δ(G), an arithmetic contradiction closed by omega.
uses
Finset.card_le_card_of_injectivehave hcard := Finset.card_le_card_of_injective (s := G.neighborFinset u) (t := C) hinj rw [G.card_neighborFinset_eq_degree] at hcard have hmin := G.minDegree_le_degree u omega
The cut edges between Xᶜ and (Xᶜ)ᶜ are the same as the cut edges between X and Xᶜ.
By double complementation, (Xᶜ)ᶜ = X. Since undirected edges are unordered pairs s(a, b) = s(b, a), an edge connects Xᶜ and (Xᶜ)ᶜ if and only if it connects X and Xᶜ.
uses
Finset.filter_congr,Finset.mem_compl,not_not,Sym2.eq_swapclassical apply Finset.filter_congr intro e _ simp only [Finset.mem_compl] constructor · rintro ⟨a, ha, b, hb, rfl⟩ rw [not_not] at hb exact ⟨b, hb, a, ha, Sym2.eq_swap⟩ · rintro ⟨a, ha, b, hb, rfl⟩ exact ⟨b, hb, a, by rw [not_not]; exact ha, Sym2.eq_swap⟩
Setting Y = Xᶜ, the cut (Y, Yᶜ) also has strictly fewer edges than δ(G).
Rewriting using exists_cut_interior_pair_dist_three_aux_cut_compl, the edges crossing the cut (Y, Yᶜ) are precisely the edges crossing (X, Xᶜ), so their number is strictly less than δ(G).
uses
exists_cut_interior_pair_dist_three_aux_cut_complclassical let Y : Finset V := (Xᶜ : Finset V) have hkY : (G.edgeFinset.filter (fun e => ∃ a ∈ Y, ∃ b ∈ (Yᶜ : Finset V), e = s(a, b))).card < G.minDegree := by dsimp [Y] rw [exists_cut_interior_pair_dist_three_aux_cut_compl] exact hk
There exist an interior vertex y ∈ X and an interior vertex x ∈ Xᶜ, each adjacent to one end of a crossing edge.
By exists_cut_interior_pair_dist_three_aux_cut, there exists an edge ab with a ∈ X and b ∈ Xᶜ = Y. Applying exists_cut_interior_pair_dist_three_aux_interior to X and a ∈ X gives a neighbor y ∈ X of a with no neighbors in Xᶜ. Symmetrically, applying it to Y and b ∈ Y gives a neighbor x ∈ Y = Xᶜ of b with no neighbors in Yᶜ = X.
uses
exists_cut_interior_pair_dist_three_aux_cut,exists_cut_interior_pair_dist_three_aux_interiorobtain ⟨a, haX, b, hbY, hab⟩ := exists_cut_interior_pair_dist_three_aux_cut G hG X hX1 hX2 obtain ⟨y, hyX, hay, hy_int⟩ := exists_cut_interior_pair_dist_three_aux_interior G X hk a haX obtain ⟨x, hxY, hbx, hx_int⟩ := exists_cut_interior_pair_dist_three_aux_interior G Y hkY b hbY have hx_intX : ∀ u ∈ X, ¬ G.Adj x u := by intro u hu exact hx_int u (by dsimp [Y] at hu ⊢; simpa using hu) have hx_mem : x ∈ (Xᶜ : Finset V) := by simpa [Y] using hxY have hy_mem : y ∈ X := hyX have hy_intY : ∀ w ∈ (Xᶜ : Finset V), ¬ G.Adj y w := hy_int
The distance between x and y is at most 3.
Concatenating the edges ya, ab, and bx produces a walk of length 3 from y to x. The distance between two vertices is bounded by the length of any connecting walk, and distance is symmetric, so dist(x, y) ≤ 3.
uses
SimpleGraph.Walk.cons,SimpleGraph.Walk.nil,SimpleGraph.dist_commlet p : G.Walk y x := SimpleGraph.Walk.cons hay.symm (SimpleGraph.Walk.cons hab (SimpleGraph.Walk.cons hbx (SimpleGraph.Walk.nil))) have hp : p.length = 3 := by simp [p] have hle : G.dist x y ≤ 3 := by have hpy : G.dist y x ≤ p.length := G.dist_le p rw [hp] at hpy rwa [SimpleGraph.dist_comm] at hpy
The vertices x and y are distinct, non-adjacent, and share no common neighbors.
First, x ≠ y because x ∈ Xᶜ and y ∈ X. Second, x is not adjacent to y because y ∈ X and x has no neighbors in X. Third, if z were a common neighbor of x and y, then z would be in either X or Xᶜ: if z ∈ X, this contradicts x having no neighbors in X; if z ∈ Xᶜ, this contradicts y having no neighbors in Xᶜ. Thus their set of common neighbors is empty.
uses
Finset.mem_compl,Set.not_nonempty_iff_eq_emptyhave hxy_ne : x ≠ y := by intro hxy have hxX : x ∈ X := by rw [hxy]; exact hy_mem rw [Finset.mem_compl] at hx_mem exact hx_mem hxX have hxy_not_adj : ¬ G.Adj x y := hx_intX y hy_mem have hcommon : G.commonNeighbors x y = ∅ := by rw [← Set.not_nonempty_iff_eq_empty] intro hne obtain ⟨z, hz⟩ := hne rw [G.mem_commonNeighbors] at hz obtain ⟨hxz, hyz⟩ := hz by_cases hzX : z ∈ X · exact hx_intX z hzX hxz · have hzY : z ∈ (Xᶜ : Finset V) := by rw [Finset.mem_compl]; exact hzX exact hy_intY z hzY hyz
The distance dist(x, y) is strictly greater than 2, and therefore equals 3.
Because x ≠ y, x is not adjacent to y, and they have no common neighbors, their extended distance satisfies edist(x, y) > 2 by SimpleGraph.two_lt_edist_iff. In a connected graph, ordinary distance coerces to extended distance, giving dist(x, y) > 2. Combined with dist(x, y) ≤ 3, linear integer arithmetic forces dist(x, y) = 3.
uses
SimpleGraph.two_lt_edist_iffhave hed : 2 < G.edist x y := by rw [SimpleGraph.two_lt_edist_iff] exact ⟨hxy_ne, hxy_not_adj, hcommon⟩ have hcast : (G.dist x y : ℕ∞) = G.edist x y := (hG x y).coe_dist_eq_edist have h2dist : 2 < G.dist x y := by have h2 : (2 : ℕ∞) < (G.dist x y : ℕ∞) := by rw [hcast] exact hed exact_mod_cast h2 have hdist : G.dist x y = 3 := by omega
The pair (x, y) satisfies all required conditions of the theorem.
The vertices x ∈ Xᶜ and y ∈ X satisfy dist(x, y) = 3, x has no neighbors in X, and y has no neighbors in Xᶜ.
exact ⟨x, y, hdist, hx_mem, hx_intX, hy_mem, hy_intY⟩
Nat.le_of_succ_le- If n + 1 ≤ m, then n ≤ m.
Finset.mem_compl- An element belongs to the complement sᶜ if and only if it does not belong to s.
le_rfl- Every element is less than or equal to itself in a preorder.
SimpleGraph.Walk.getVert_length- The vertex at index equal to the walk's length is the walk's terminal vertex.
exists_cut_interior_pair_dist_three_aux_walk- Any walk between a vertex in X and a vertex in Xᶜ must traverse at least one edge with one endpoint in X and the other in Xᶜ.
Classical.choose- Given a non-empty existential proposition ∃ x, P x, returns a chosen witness x.
Classical.choose_spec- The witness chosen by Classical.choose satisfies the existential predicate P.
Finset.mem_filter.mpr- An element belongs to a filtered finset if it belongs to the base set and satisfies the filter predicate.
congrArg- Applying a function to equal arguments yields equal results.
Subtype.val- Projects an element of a subtype to its underlying type.
Sym2.eq_iff- Two unordered pairs s(x, y) and s(z, w) are equal if and only if (x = z ∧ y = w) or (x = w ∧ y = z).
Subtype.ext- Two subtype terms are equal if their underlying values are equal.
Finset.card_le_card_of_injective- An injective map between finite sets implies the cardinality of the domain is at most the cardinality of the codomain.
Finset.filter_congr- If two predicates are pointwise equivalent on a finset, filtering by either predicate produces the same finset.
not_not- Double negation elimination: ¬¬P ↔ P.
Sym2.eq_swap- An unordered pair is symmetric: s(a, b) = s(b, a).
exists_cut_interior_pair_dist_three_aux_cut_compl- The cut edges between Xᶜ and (Xᶜ)ᶜ equal the cut edges between X and Xᶜ.
exists_cut_interior_pair_dist_three_aux_cut- In a connected graph, any non-trivial cut has at least one crossing edge.
exists_cut_interior_pair_dist_three_aux_interior- If a cut (S, Sᶜ) has fewer edges than the minimum degree δ(G), every vertex in S has a neighbor in S with no neighbors in Sᶜ.
SimpleGraph.Walk.cons- Prepends an edge to a walk, creating a walk from the new vertex to the original walk's destination.
SimpleGraph.Walk.nil- The trivial walk of length 0 from a vertex to itself.
SimpleGraph.dist_comm- Graph distance is symmetric: dist(u, v) = dist(v, u).
Set.not_nonempty_iff_eq_empty- A set is not nonempty if and only if it is the empty set.
SimpleGraph.two_lt_edist_iff- The extended distance edist(u, v) is strictly greater than 2 if and only if u ≠ v, u is not adjacent to v, and u and v share no common neighbors.
- The hypothesis `hd : 3 ≤ G.diam` is present in the signature of `exists_cut_interior_pair_dist_three` but is not used anywhere in the proof, as the distance 3 pair is constructed directly from the cut condition.
- Classical reasoning (`classical`, `Classical.choose`, `Classical.choose_spec`) is used to pick crossing edges and witnesses for interior vertices.
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.
lemma exists_cut_interior_pair_dist_three_aux_walk {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (X : Finset V) {u v : V} (p : G.Walk u v) (hu : u ∈ X) (hv : v ∈ (Xᶜ : Finset V)) : ∃ a ∈ X, ∃ b ∈ (Xᶜ : Finset V), G.Adj a b := by by_contra h push_neg at h have hstay : ∀ i ≤ p.length, p.getVert i ∈ X := by intro i induction i with | zero => intro _ simpa using hu | succ n ih => intro hn have hnX : p.getVert n ∈ X := ih (Nat.le_of_succ_le hn) by_contra hc have hcY : p.getVert (n + 1) ∈ (Xᶜ : Finset V) := by rw [Finset.mem_compl] exact hc exact h (p.getVert n) hnX (p.getVert (n + 1)) hcY (p.adj_getVert_succ hn) have hp : p.getVert p.length ∈ X := hstay p.length le_rfl have hvY : p.getVert p.length ∈ (Xᶜ : Finset V) := by simpa [SimpleGraph.Walk.getVert_length] using hv rw [Finset.mem_compl] at hvY exact hvY hplemma exists_cut_interior_pair_dist_three_aux_cut {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (X : Finset V) (hX1 : X.Nonempty) (hX2 : (Xᶜ : Finset V).Nonempty) : ∃ a ∈ X, ∃ b ∈ (Xᶜ : Finset V), G.Adj a b := by obtain ⟨a, ha⟩ := hX1 obtain ⟨b, hb⟩ := hX2 obtain ⟨p⟩ := hG.preconnected a b exact exists_cut_interior_pair_dist_three_aux_walk G X p ha hblemma exists_cut_interior_pair_dist_three_aux_interior {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (S : Finset V) (hk : (G.edgeFinset.filter (fun e => ∃ a ∈ S, ∃ b ∈ (Sᶜ : Finset V), e = s(a, b))).card < G.minDegree) (u : V) (hu : u ∈ S) : ∃ y ∈ S, G.Adj u y ∧ ∀ z ∈ (Sᶜ : Finset V), ¬ G.Adj y z := by classical by_contra hcon push_neg at hcon let C := G.edgeFinset.filter (fun e => ∃ a ∈ S, ∃ b ∈ (Sᶜ : Finset V), e = s(a, b)) change C.card < G.minDegree at hk let f : ↥(G.neighborFinset u) → ↥C := fun y => if hy : (y : V) ∈ S then ⟨s((y : V), Classical.choose (hcon (y : V) hy ((G.mem_neighborFinset u (y : V)).mp y.2))), by obtain ⟨hzY, hzy⟩ := Classical.choose_spec (hcon (y : V) hy ((G.mem_neighborFinset u (y : V)).mp y.2)) refine Finset.mem_filter.mpr ⟨?_, ?_⟩ · exact (G.mem_edgeFinset).mpr ((G.mem_edgeSet).mpr hzy) · exact ⟨(y : V), hy, _, hzY, rfl⟩⟩ else ⟨s(u, (y : V)), by refine Finset.mem_filter.mpr ⟨?_, ?_⟩ · exact (G.mem_edgeFinset).mpr ((G.mem_edgeSet).mpr ((G.mem_neighborFinset u (y : V)).mp y.2)) · refine ⟨u, hu, (y : V), ?_, rfl⟩ rw [Finset.mem_compl] exact hy⟩ have hinj : Function.Injective f := by intro y1 y2 h have hval : (f y1).1 = (f y2).1 := congrArg Subtype.val h simp only [f] at hval split_ifs at hval with hy1 hy2 hy2 hy1 · have adj1 : G.Adj u ↑y1 := (G.mem_neighborFinset u ↑y1).mp y1.2 have adj2 : G.Adj u ↑y2 := (G.mem_neighborFinset u ↑y2).mp y2.2 rw [Sym2.eq_iff] at hval obtain ⟨h1, h2⟩ | ⟨h1, h2⟩ := hval · exact Subtype.ext h1 · exfalso have hz2Y : Classical.choose (hcon ↑y2 hy2 adj2) ∈ (Sᶜ : Finset V) := (Classical.choose_spec (hcon ↑y2 hy2 adj2)).1 have hY : ↑y1 ∈ (Sᶜ : Finset V) := h1.symm ▸ hz2Y rw [Finset.mem_compl] at hY exact hY hy1 · exfalso have adj1 : G.Adj u ↑y1 := (G.mem_neighborFinset u ↑y1).mp y1.2 have adj2 : G.Adj u ↑y2 := (G.mem_neighborFinset u ↑y2).mp y2.2 have hz1Y : Classical.choose (hcon ↑y1 hy1 adj1) ∈ (Sᶜ : Finset V) := (Classical.choose_spec (hcon ↑y1 hy1 adj1)).1 rw [Sym2.eq_iff] at hval obtain ⟨h1, h2⟩ | ⟨h1, h2⟩ := hval · exact adj1.ne' h1 · exact hy2 (h1 ▸ hy1) · exfalso have adj1 : G.Adj u ↑y1 := (G.mem_neighborFinset u ↑y1).mp y1.2 have adj2 : G.Adj u ↑y2 := (G.mem_neighborFinset u ↑y2).mp y2.2 have hz2Y : Classical.choose (hcon ↑y2 hy2 adj2) ∈ (Sᶜ : Finset V) := (Classical.choose_spec (hcon ↑y2 hy2 adj2)).1 rw [Sym2.eq_iff] at hval obtain ⟨h1, h2⟩ | ⟨h1, h2⟩ := hval · exact adj2.ne h1 · rw [Finset.mem_compl] at hz2Y exact hz2Y (h1 ▸ hu) · have adj1 : G.Adj u ↑y1 := (G.mem_neighborFinset u ↑y1).mp y1.2 have adj2 : G.Adj u ↑y2 := (G.mem_neighborFinset u ↑y2).mp y2.2 rw [Sym2.eq_iff] at hval obtain ⟨h1, h2⟩ | ⟨h1, h2⟩ := hval · exact Subtype.ext h2 · exfalso exact hy1 (h2.symm ▸ hu) have hcard := Finset.card_le_card_of_injective (s := G.neighborFinset u) (t := C) hinj rw [G.card_neighborFinset_eq_degree] at hcard have hmin := G.minDegree_le_degree u omegalemma exists_cut_interior_pair_dist_three_aux_cut_compl {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (X : Finset V) : (G.edgeFinset.filter (fun e => ∃ a ∈ (Xᶜ : Finset V), ∃ b ∈ ((Xᶜ : Finset V)ᶜ : Finset V), e = s(a, b))) = (G.edgeFinset.filter (fun e => ∃ a ∈ X, ∃ b ∈ (Xᶜ : Finset V), e = s(a, b))) := by classical apply Finset.filter_congr intro e _ simp only [Finset.mem_compl] constructor · rintro ⟨a, ha, b, hb, rfl⟩ rw [not_not] at hb exact ⟨b, hb, a, ha, Sym2.eq_swap⟩ · rintro ⟨a, ha, b, hb, rfl⟩ exact ⟨b, hb, a, by rw [not_not]; exact ha, Sym2.eq_swap⟩/-- In a connected graph with |E(X, Xᶜ)| < δ(G) and diam(G) ≥ 3, there exists an interior pair at distance 3. -/theorem exists_cut_interior_pair_dist_three {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (hd : 3 ≤ G.diam) (X : Finset V) (hX1 : X.Nonempty) (hX2 : (Xᶜ : Finset V).Nonempty) (hk : (G.edgeFinset.filter (fun e => ∃ u ∈ X, ∃ v ∈ (Xᶜ : Finset V), e = s(u, v))).card < G.minDegree) : ∃ (x y : V), G.dist x y = 3 ∧ x ∈ (Xᶜ : Finset V) ∧ (∀ u ∈ X, ¬ G.Adj x u) ∧ y ∈ X ∧ (∀ w ∈ (Xᶜ : Finset V), ¬ G.Adj y w) := by classical let Y : Finset V := (Xᶜ : Finset V) have hkY : (G.edgeFinset.filter (fun e => ∃ a ∈ Y, ∃ b ∈ (Yᶜ : Finset V), e = s(a, b))).card < G.minDegree := by dsimp [Y] rw [exists_cut_interior_pair_dist_three_aux_cut_compl] exact hk obtain ⟨a, haX, b, hbY, hab⟩ := exists_cut_interior_pair_dist_three_aux_cut G hG X hX1 hX2 obtain ⟨y, hyX, hay, hy_int⟩ := exists_cut_interior_pair_dist_three_aux_interior G X hk a haX obtain ⟨x, hxY, hbx, hx_int⟩ := exists_cut_interior_pair_dist_three_aux_interior G Y hkY b hbY have hx_intX : ∀ u ∈ X, ¬ G.Adj x u := by intro u hu exact hx_int u (by dsimp [Y] at hu ⊢; simpa using hu) have hx_mem : x ∈ (Xᶜ : Finset V) := by simpa [Y] using hxY have hy_mem : y ∈ X := hyX have hy_intY : ∀ w ∈ (Xᶜ : Finset V), ¬ G.Adj y w := hy_int let p : G.Walk y x := SimpleGraph.Walk.cons hay.symm (SimpleGraph.Walk.cons hab (SimpleGraph.Walk.cons hbx (SimpleGraph.Walk.nil))) have hp : p.length = 3 := by simp [p] have hle : G.dist x y ≤ 3 := by have hpy : G.dist y x ≤ p.length := G.dist_le p rw [hp] at hpy rwa [SimpleGraph.dist_comm] at hpy have hxy_ne : x ≠ y := by intro hxy have hxX : x ∈ X := by rw [hxy]; exact hy_mem rw [Finset.mem_compl] at hx_mem exact hx_mem hxX have hxy_not_adj : ¬ G.Adj x y := hx_intX y hy_mem have hcommon : G.commonNeighbors x y = ∅ := by rw [← Set.not_nonempty_iff_eq_empty] intro hne obtain ⟨z, hz⟩ := hne rw [G.mem_commonNeighbors] at hz obtain ⟨hxz, hyz⟩ := hz by_cases hzX : z ∈ X · exact hx_intX z hzX hxz · have hzY : z ∈ (Xᶜ : Finset V) := by rw [Finset.mem_compl]; exact hzX exact hy_intY z hzY hyz have hed : 2 < G.edist x y := by rw [SimpleGraph.two_lt_edist_iff] exact ⟨hxy_ne, hxy_not_adj, hcommon⟩ have hcast : (G.dist x y : ℕ∞) = G.edist x y := (hG x y).coe_dist_eq_edist have h2dist : 2 < G.dist x y := by have h2 : (2 : ℕ∞) < (G.dist x y : ℕ∞) := by rw [hcast] exact hed exact_mod_cast h2 have hdist : G.dist x y = 3 := by omega exact ⟨x, y, hdist, hx_mem, hx_intX, hy_mem, hy_intY⟩