AFTD Auto-Formalizing Theoretical Domains

exists_cut_interior_pair_dist_three

theoremverified

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.

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

    lines 5–20

    uses Nat.le_of_succ_le, Finset.mem_compl

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

    lines 21–25

    uses le_rfl, SimpleGraph.Walk.getVert_length, Finset.mem_compl

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

    lines 32–35

    uses exists_cut_interior_pair_dist_three_aux_walk

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

    lines 44–48

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

    lines 49–62

    uses Classical.choose, Classical.choose_spec, Finset.mem_filter.mpr, Finset.mem_compl

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

    lines 63–104

    uses congrArg, Subtype.val, Sym2.eq_iff, Subtype.ext, Classical.choose, Classical.choose_spec, Finset.mem_compl

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

    lines 105–108

    uses Finset.card_le_card_of_injective

      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
      omega
  8. 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ᶜ.

    lines 115–124

    uses Finset.filter_congr, Finset.mem_compl, not_not, Sym2.eq_swap

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

    lines 137–143

    uses exists_cut_interior_pair_dist_three_aux_cut_compl

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

    lines 144–155

    uses exists_cut_interior_pair_dist_three_aux_cut, exists_cut_interior_pair_dist_three_aux_interior

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

    lines 156–162

    uses SimpleGraph.Walk.cons, SimpleGraph.Walk.nil, SimpleGraph.dist_comm

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

    lines 163–178

    uses Finset.mem_compl, Set.not_nonempty_iff_eq_empty

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

    lines 179–188

    uses SimpleGraph.two_lt_edist_iff

      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
  14. 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ᶜ.

    line 189

      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.

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

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