AFTD Auto-Formalizing Theoretical Domains

connected_cubic_bipartite_has_no_cut_vertex

theoremverifiedformalization

Every finite connected cubic bipartite graph has no cut vertex: deleting any single vertex leaves a preconnected induced subgraph.

Statement

theorem connected_cubic_bipartite_has_no_cut_vertex
    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
    (hconn : G.Connected) (hreg : G.IsRegularOfDegree 3) (hbip : G.IsBipartite)
    (v : V) : (G.induce {v}ᶜ).Preconnected
Formalizes
arXiv:2611.16649 Sec. 3.4, p. 10
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

Read back from the Lean

Let $V$ be a finite type with decidable equality, and let $G$ be a simple graph on $V$ with decidable adjacency. Assume that: 1. $G$ is connected (G.Connected); 2. $G$ is regular of degree 3 (G.IsRegularOfDegree 3); and 3. $G$ is bipartite (G.IsBipartite). Then, for every vertex $v : V$, the induced subgraph on $V \setminus \{v\}$ (G.induce {v}ᶜ) is preconnected (meaning that any two vertices distinct from $v$ can be joined by a path in $G$ that does not pass through $v$, i.e., $v$ is not a cut vertex).

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 proceeds by contradiction: assuming that deleting a vertex v disconnects the graph, let C1 be a connected component in G \\ {v} and partition C1 into A1 (vertices with the same color as v) and B1 (vertices with the opposite color). Double-counting the bipartite edges between A1 and B1 shows that the number k of edges between v and C1 satisfies 3|A1| + k = 3|B1|, forcing 3 to divide k. Since G is 3-regular, k must be either 0 or 3; however, the connectivity of G implies that k cannot be 0 (otherwise C1 has no edges to the rest of the graph) nor 3 (otherwise C1 ∪ {v} has no edges to the rest of the graph), yielding a contradiction.

  1. In the two-element set Fin 2, any two elements distinct from a third element are equal. automation

    Since Fin 2 contains only two elements, any two elements both distinct from c must coincide with the unique other element, verified by finite exhaustion using `decide`.

    lines 1–5

    private lemma connected_cubic_bipartite_has_no_cut_vertex_fin2_eq_of_ne_of_ne {a b c : Fin 2}
        (h1 : a ≠ c) (h2 : b ≠ c) : a = b := by
      revert a b c
      decide
    
  2. In a connected graph, any non-empty proper subset of vertices has an edge crossing to its complement.

    Given vertices u ∈ S and w ∉ S, connectedness provides a walk from u to w. A boundary dart of this walk that exits S provides vertices a ∈ S and b ∉ S that are adjacent in G.

    lines 6–13

    private lemma connected_cubic_bipartite_has_no_cut_vertex_exists_adj_of_connected
        {V : Type*} (G : SimpleGraph V) (hconn : G.Connected)
        (S : Set V) {u : V} (hu : u ∈ S) {w : V} (hw : w ∉ S) :
        ∃ a ∈ S, ∃ b ∉ S, G.Adj a b := by
      obtain ⟨p⟩ := hconn.preconnected u w
      obtain ⟨d, _, h1, h2⟩ := p.exists_boundary_dart S hu hw
      exact ⟨d.toProd.1, h1, d.toProd.2, h2, d.adj⟩
    
  3. For any two finsets of vertices A1 and B1, the sum of degrees from A1 into B1 equals the sum of degrees from B1 into A1.

    Each neighborhood size is expressed as a sum of 0-1 indicators using `Finset.card_filter`. By the symmetry of adjacency (`if_pos`, `if_neg`, `Finset.sum_congr`), interchanging the summation order using `Finset.sum_comm` shows that counting cross-edges from A1 or from B1 gives the same total.

    lines 14–31

    uses Finset.card_filter, Finset.sum_congr, if_pos, if_neg, Finset.sum_comm

    private lemma connected_cubic_bipartite_has_no_cut_vertex_sum_bipartite_edges
        {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
        (A1 B1 : Finset V) :
        ∑ u ∈ A1, (B1.filter (G.Adj u)).card = ∑ w ∈ B1, (A1.filter (G.Adj w)).card := by
      have h1 : ∀ u, (B1.filter (G.Adj u)).card = ∑ w ∈ B1, (if G.Adj u w then 1 else 0) := by
        intro u
        rw [Finset.card_filter]
      have h2 : ∀ w, (A1.filter (G.Adj w)).card = ∑ u ∈ A1, (if G.Adj u w then 1 else 0) := by
        intro w
        rw [Finset.card_filter]
        apply Finset.sum_congr rfl
        intro u _
        by_cases h : G.Adj u w
        · rw [if_pos h, if_pos (G.adj_symm h)]
        · rw [if_neg h, if_neg (fun h' => h (G.adj_symm h'))]
      simp_rw [h1, h2]
      exact Finset.sum_comm
    
  4. Assume for contradiction that G \\ {v} is not preconnected, and fix two mutually unreachable vertices x and y, and a 2-coloring c.

    Unfolding `SimpleGraph.Preconnected`, we assume for contradiction that there exist vertices x and y in the induced subgraph on {v}ᶜ with no walk between them. Since G is bipartite, we also obtain a proper 2-coloring c : V → Fin 2.

    lines 32–41

    uses SimpleGraph.Preconnected

    /-- Every connected cubic bipartite graph has no cut vertex: deleting any single vertex leaves a preconnected induced subgraph. -/
    theorem connected_cubic_bipartite_has_no_cut_vertex
        {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
        (hconn : G.Connected) (hreg : G.IsRegularOfDegree 3) (hbip : G.IsBipartite)
        (v : V) : (G.induce {v}ᶜ).Preconnected := by
      classical
      rw [SimpleGraph.Preconnected]
      by_contra! hnot
      obtain ⟨x, y, hxy⟩ := hnot
      obtain ⟨c⟩ := hbip
  5. The set C1 of vertices reachable from x in G \\ {v} contains x, but does not contain y or v.

    Defining C1 as the finset of vertices reachable in H = G \\ {v} from x, x belongs to C1 by reflexivity of reachability (`Finset.mem_univ`, `Finset.mem_filter`, `Subtype.ext`), y does not belong to C1 because it cannot be reached from x, and v does not belong to C1 because it is not in the induced subgraph H.

    lines 42–59

    uses Finset.mem_filter, Finset.mem_univ, Subtype.ext

      let H := G.induce {v}ᶜ
      let C1 : Finset V := Finset.univ.filter (fun u => ∃ h : u ∈ ({v}ᶜ : Set V), H.Reachable x ⟨u, h⟩)
      have hC1_eq : C1 = Finset.univ.filter (fun u => ∃ h : u ∈ ({v}ᶜ : Set V), H.Reachable x ⟨u, h⟩) := rfl
      have hx : x.1 ∈ C1 := by
        rw [hC1_eq, Finset.mem_filter]
        refine ⟨Finset.mem_univ _, x.2, ?_⟩
        have : (⟨x.1, x.2⟩ : {w : V // w ∈ ({v}ᶜ : Set V)}) = x := Subtype.ext rfl
        rw [this]
      have hy : y.1 ∉ C1 := by
        rw [hC1_eq, Finset.mem_filter]
        rintro ⟨-, h, hr⟩
        have : (⟨y.1, h⟩ : {w : V // w ∈ ({v}ᶜ : Set V)}) = y := Subtype.ext rfl
        rw [this] at hr
        exact hxy hr
      have hv : v ∉ C1 := by
        rw [hC1_eq, Finset.mem_filter]
        rintro ⟨-, h, -⟩
        exact h rfl
  6. Any neighbor in G of a vertex in C1 must either belong to C1 or be v.

    For u ∈ C1 and any neighbor w of u, either w = v or w ≠ v (`Or.inr`). If w ≠ v, then w is a vertex of H adjacent to u in H (`SimpleGraph.induce_adj`), so reachability from x extends across this edge to w, which places w in C1 (`Finset.mem_univ`, `Finset.mem_filter`).

    lines 60–72

    uses Or.inr, Finset.mem_filter, Finset.mem_univ, SimpleGraph.induce_adj

      have hadj : ∀ {u w}, u ∈ C1 → G.Adj u w → w ∈ C1 ∨ w = v := by
        intro u w hu hadj
        by_cases hw : w = v
        · exact Or.inr hw
        · left
          rw [hC1_eq, Finset.mem_filter] at hu ⊢
          obtain ⟨-, hu_ne, hr⟩ := hu
          have hw_mem : w ∈ ({v}ᶜ : Set V) := hw
          refine ⟨Finset.mem_univ _, hw_mem, ?_⟩
          have hadjH : H.Adj ⟨u, hu_ne⟩ ⟨w, hw_mem⟩ := by
            rw [SimpleGraph.induce_adj]
            exact hadj
          exact hr.trans hadjH.reachable
  7. Partition C1 into A1 (same color as v) and B1 (different color from v); then every vertex in A1 has exactly 3 neighbors in B1.

    For u ∈ A1, any neighbor w has color c(w) ≠ c(u) = c(v), so w cannot be v. All neighbors of u must therefore belong to C1, and having color distinct from v puts them in B1. Since G is 3-regular, each u ∈ A1 has degree 3 in G, so its neighborhood in B1 has cardinality 3 (`Finset.mem_filter`, `SimpleGraph.mem_neighborFinset`, `congr_arg`).

    lines 73–98

    uses Finset.mem_filter, SimpleGraph.mem_neighborFinset, congr_arg

      let A1 := C1.filter (fun u => c u = c v)
      let B1 := C1.filter (fun u => c u ≠ c v)
      have hB1_eq : B1 = C1.filter (fun u => c u ≠ c v) := rfl
      have h_A1_deg : ∀ u ∈ A1, (B1.filter (G.Adj u)).card = 3 := by
        intro u hu
        rw [Finset.mem_filter] at hu
        have hsub : ∀ w, G.Adj u w → w ∈ B1 := by
          intro w hw
          have hc : c u ≠ c w := (c.map_rel hw).ne
          have hcases := hadj hu.1 hw
          rw [Finset.mem_filter]
          obtain hw_c1 | rfl := hcases
          · refine ⟨hw_c1, ?_⟩
            intro hcw
            rw [hu.2, hcw] at hc
            exact hc rfl
          · exfalso
            exact hc hu.2
        have h_eq : B1.filter (G.Adj u) = G.neighborFinset u := by
          ext w
          simp only [Finset.mem_filter, SimpleGraph.mem_neighborFinset]
          constructor
          · rintro ⟨-, hw⟩; exact hw
          · intro hw; exact ⟨hsub w hw, hw⟩
        have hd : (B1.filter (G.Adj u)).card = G.degree u := congr_arg Finset.card h_eq
        rw [hd, hreg u]
  8. For every vertex w ∈ B1, the number of its neighbors in A1 plus 1 if w is adjacent to v equals 3.

    For w ∈ B1, any neighbor z of w has color c(z) ≠ c(w). Because c(w) ≠ c(v) in Fin 2, lemma `connected_cubic_bipartite_has_no_cut_vertex_fin2_eq_of_ne_of_ne` forces c(z) = c(v). Since all neighbors of w lie in C1 ∪ {v}, those in C1 have color c(v) and thus lie in A1. Hence the neighbors of w are precisely its neighbors in A1, plus v if w is adjacent to v. Since w has degree 3, the sum of its degree into A1 and the indicator of adjacency to v equals 3 (`Finset.card_insert_of_notMem`, `SimpleGraph.mem_neighborFinset`, `Finset.mem_insert`, `Or.inl`, `Or.inr`, `congr_arg`).

    lines 99–145

    uses Finset.mem_filter, connected_cubic_bipartite_has_no_cut_vertex_fin2_eq_of_ne_of_ne, SimpleGraph.mem_neighborFinset, Finset.mem_insert, Or.inr, Or.inl, Finset.card_insert_of_notMem, congr_arg

      have h_B1_deg : ∀ w ∈ B1, (A1.filter (G.Adj w)).card + (if G.Adj w v then 1 else 0) = 3 := by
        intro w hw
        rw [Finset.mem_filter] at hw
        have hvA1 : v ∉ A1 := fun h => hv (Finset.mem_filter.mp h).1
        have hsub : ∀ z, G.Adj w z → z ∈ A1 ∨ z = v := by
          intro z hz
          have hc : c z ≠ c w := (c.map_rel hz).symm.ne
          have hcases := hadj hw.1 hz
          obtain hz_c1 | rfl := hcases
          · left
            rw [Finset.mem_filter]
            refine ⟨hz_c1, ?_⟩
            exact connected_cubic_bipartite_has_no_cut_vertex_fin2_eq_of_ne_of_ne hc hw.2.symm
          · right
            rfl
        by_cases hadjv : G.Adj w v
        · simp only [hadjv, ite_true]
          have h_eq : G.neighborFinset w = insert v (A1.filter (G.Adj w)) := by
            ext z
            simp only [SimpleGraph.mem_neighborFinset, Finset.mem_insert, Finset.mem_filter]
            constructor
            · intro hz
              obtain hz' | rfl := hsub z hz
              · exact Or.inr ⟨hz', hz⟩
              · exact Or.inl rfl
            · rintro (rfl | ⟨-, hz⟩)
              · exact hadjv
              · exact hz
          have hv_not_mem : v ∉ A1.filter (G.Adj w) := by
            simp [hvA1]
          have hd : G.degree w = (insert v (A1.filter (G.Adj w))).card := congr_arg Finset.card h_eq
          rw [Finset.card_insert_of_notMem hv_not_mem] at hd
          have := hreg w
          omega
        · simp only [hadjv, ite_false, add_zero]
          have h_eq : G.neighborFinset w = A1.filter (G.Adj w) := by
            ext z
            simp only [SimpleGraph.mem_neighborFinset, Finset.mem_filter]
            constructor
            · intro hz
              obtain hz' | rfl := hsub z hz
              · exact ⟨hz', hz⟩
              · exact (hadjv hz).elim
            · rintro ⟨-, hz⟩
              exact hz
          have hd : G.degree w = (A1.filter (G.Adj w)).card := congr_arg Finset.card h_eq
          rw [← hd, hreg w]
  9. The number k of neighbors of v in C1 is divisible by 3.

    Summing degrees over A1 gives 3|A1| (`Finset.sum_congr`, `mul_comm`). Summing degrees over B1 plus the adjacency indicators to v gives 3|B1| (`Finset.card_filter`, `Finset.sum_add_distrib`). Since neighbors of v must have color different from v, all neighbors of v in C1 belong to B1, so k equals the number of neighbors of v in B1. By `connected_cubic_bipartite_has_no_cut_vertex_sum_bipartite_edges`, the cross-edges between A1 and B1 cancel, yielding 3|A1| + k = 3|B1|. Therefore k = 3(|B1| - |A1|), which is divisible by 3 (`dvd_mul_right`).

    lines 146–176

    uses Finset.sum_congr, mul_comm, Finset.card_filter, Finset.sum_add_distrib, Finset.mem_filter, connected_cubic_bipartite_has_no_cut_vertex_sum_bipartite_edges, dvd_mul_right

      have h_sum_A1 : ∑ u ∈ A1, (B1.filter (G.Adj u)).card = 3 * A1.card := by
        have : ∑ u ∈ A1, (B1.filter (G.Adj u)).card = ∑ u ∈ A1, 3 := Finset.sum_congr rfl h_A1_deg
        rw [this]
        simp [mul_comm]
      have h_sum_B1 : (∑ w ∈ B1, (A1.filter (G.Adj w)).card) + (B1.filter (fun w => G.Adj w v)).card = 3 * B1.card := by
        have h_card : (B1.filter (fun w => G.Adj w v)).card = ∑ w ∈ B1, (if G.Adj w v then 1 else 0) := by
          rw [Finset.card_filter]
        rw [h_card, ← Finset.sum_add_distrib]
        have : ∑ w ∈ B1, ((A1.filter (G.Adj w)).card + (if G.Adj w v then 1 else 0)) = ∑ w ∈ B1, 3 :=
          Finset.sum_congr rfl h_B1_deg
        rw [this]
        simp [mul_comm]
      have h_filter_eq : B1.filter (fun w => G.Adj w v) = C1.filter (fun w => G.Adj w v) := by
        rw [hB1_eq]
        ext w
        simp only [Finset.mem_filter]
        constructor
        · rintro ⟨⟨hw, -⟩, hadj'⟩
          exact ⟨hw, hadj'⟩
        · rintro ⟨hw, hadj'⟩
          have hc : c w ≠ c v := (c.map_rel hadj').ne
          exact ⟨⟨hw, hc⟩, hadj'⟩
      let k := (C1.filter (fun w => G.Adj w v)).card
      have hdvd : 3 ∣ k := by
        have h_edges := connected_cubic_bipartite_has_no_cut_vertex_sum_bipartite_edges G A1 B1
        have hk_eq : k = (B1.filter (fun w => G.Adj w v)).card := h_filter_eq.symm ▸ rfl
        have h_eq : 3 * A1.card + k = 3 * B1.card := by
          rw [hk_eq, ← h_sum_A1, h_edges, h_sum_B1]
        have : k = 3 * (B1.card - A1.card) := by omega
        rw [this]
        exact dvd_mul_right 3 (B1.card - A1.card)
  10. k ≤ 3.

    The neighbors of v in C1 form a subset of all neighbors of v in G (`SimpleGraph.mem_neighborFinset`). Since G is 3-regular, v has degree 3, so k ≤ 3 by monotonicity of cardinality (`Finset.card_le_card`, `Finset.mem_filter`).

    lines 177–186

    uses Finset.mem_filter, SimpleGraph.mem_neighborFinset, Finset.card_le_card

      have hk_sub : C1.filter (fun w => G.Adj w v) ⊆ G.neighborFinset v := by
        intro w hw
        rw [Finset.mem_filter] at hw
        rw [SimpleGraph.mem_neighborFinset]
        exact hw.2.symm
      have hdeg : G.degree v = 3 := hreg v
      have hk_le : k ≤ 3 := by
        have := Finset.card_le_card hk_sub
        rw [← hdeg]
        exact this
  11. k ≠ 0.

    If k = 0, there are no edges between C1 and v. Because G is connected, x ∈ C1, and v ∉ C1, lemma `connected_cubic_bipartite_has_no_cut_vertex_exists_adj_of_connected` yields an edge between some a ∈ C1 and b ∉ C1. Since every neighbor of a must lie in C1 or equal v, we must have b = v, meaning a ∈ C1 is adjacent to v, so k > 0 (`Finset.card_pos`), contradicting k = 0.

    lines 187–200

    uses Finset.mem_coe, connected_cubic_bipartite_has_no_cut_vertex_exists_adj_of_connected, Finset.mem_filter, Finset.card_pos

      have hk_ne_zero : k ≠ 0 := by
        intro hk0
        have hv' : (v : V) ∉ (C1 : Set V) := fun h => hv (Finset.mem_coe.mp h)
        obtain ⟨a, ha, b, hb, hab⟩ := connected_cubic_bipartite_has_no_cut_vertex_exists_adj_of_connected G hconn (C1 : Set V) (Finset.mem_coe.mpr hx) hv'
        rw [Finset.mem_coe] at ha hb
        have hcases := hadj ha hab
        obtain hb_c1 | hb_v := hcases
        · exact hb hb_c1
        · rw [hb_v] at hab
          have ha_mem : a ∈ C1.filter (fun w => G.Adj w v) := by
            rw [Finset.mem_filter]
            exact ⟨ha, hab⟩
          have : 0 < (C1.filter (fun w => G.Adj w v)).card := Finset.card_pos.mpr ⟨a, ha_mem⟩
          omega
  12. k ≠ 3.

    If k = 3, all 3 neighbors of v lie in C1 (`Finset.eq_of_subset_of_card_le`, `le_rfl`). Setting S = C1 ∪ {v}, y ∉ S since y ≠ v and y ∉ C1. Connectedness of G yields an edge between some a ∈ S and b ∉ S (`connected_cubic_bipartite_has_no_cut_vertex_exists_adj_of_connected`, `Set.mem_insert`). If a = v, b is a neighbor of v, so b ∈ C1 ⊆ S, a contradiction. If a ∈ C1, b must be in C1 or equal v, so again b ∈ S, a contradiction. Thus k ≠ 3.

    lines 201–233

    uses Finset.eq_of_subset_of_card_le, le_rfl, SimpleGraph.mem_neighborFinset, Finset.mem_filter, Finset.mem_coe, connected_cubic_bipartite_has_no_cut_vertex_exists_adj_of_connected, Set.mem_insert, Or.inr, Or.inl

      have hk_ne_three : k ≠ 3 := by
        intro hk3
        have h_eq : C1.filter (fun w => G.Adj w v) = G.neighborFinset v := by
          apply Finset.eq_of_subset_of_card_le hk_sub
          change (G.neighborFinset v).card ≤ k
          rw [hk3, ← hdeg]
          exact le_rfl
        have h_neigh_sub : ∀ w, G.Adj v w → w ∈ C1 := by
          intro w hw
          have : w ∈ G.neighborFinset v := by
            rw [SimpleGraph.mem_neighborFinset]
            exact hw
          rw [← h_eq, Finset.mem_filter] at this
          exact this.1
        let S : Set V := insert v (C1 : Set V)
        have hy_not_S : y.1 ∉ S := by
          intro hyS
          cases hyS with
          | inl h => exact y.2 h
          | inr h => exact hy (Finset.mem_coe.mp h)
        obtain ⟨a, ha, b, hb, hab⟩ := connected_cubic_bipartite_has_no_cut_vertex_exists_adj_of_connected G hconn S (Set.mem_insert v (C1 : Set V)) hy_not_S
        cases ha with
        | inl ha_v =>
          subst ha_v
          exact hb (Or.inr (Finset.mem_coe.mpr (h_neigh_sub b hab)))
        | inr ha_c1 =>
          rw [Finset.mem_coe] at ha_c1
          have hcases := hadj ha_c1 hab
          obtain hb_c1 | hb_v := hcases
          · exact hb (Or.inr (Finset.mem_coe.mpr hb_c1))
          · apply hb
            rw [hb_v]
            exact Or.inl rfl
  13. Contradiction, completing the proof. automation

    Since 3 divides k and 0 ≤ k ≤ 3, k must be 0 or 3, but both have been ruled out. Linear integer arithmetic (`omega`) closes the goal with False.

    lines 234–235

      obtain ⟨m, hm⟩ := hdvd
      omega
Finset.card_filter
The cardinality of a filtered finset equals the sum of indicator values (1 if the condition holds, 0 otherwise) over all elements of the set.
Finset.sum_congr
If two finsets are equal and their summands agree on all elements, their sums are equal.
if_pos
If a proposition c holds, then the conditional expression `if c then t else e` reduces to t.
if_neg
If a proposition c does not hold, then the conditional expression `if c then t else e` reduces to e.
Finset.sum_comm
In a double summation over two finite sets, the order of summation can be exchanged.
SimpleGraph.Preconnected
A simple graph is preconnected if any two of its vertices are connected by a walk (i.e. reachable from one another).
Finset.mem_filter
An element belongs to a filtered finset {x ∈ s | p x} if and only if it belongs to s and satisfies p.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
Subtype.ext
Two elements of a subtype are equal if and only if their underlying values are equal.
Or.inr
Infers a disjunction A ∨ B from a proof of B.
SimpleGraph.induce_adj
Two vertices of an induced subgraph are adjacent if and only if they are adjacent in the ambient graph.
SimpleGraph.mem_neighborFinset
A vertex w is in the neighbor finset of v if and only if v and w are adjacent.
congr_arg
Applying a function to equal arguments yields equal results (congruence of arguments).
connected_cubic_bipartite_has_no_cut_vertex_fin2_eq_of_ne_of_ne
In the two-element set Fin 2, any two elements distinct from a third element are equal.
Finset.mem_insert
An element belongs to insert a s if and only if it equals a or belongs to s.
Or.inl
Infers a disjunction A ∨ B from a proof of A.
Finset.card_insert_of_notMem
If a ∉ s, then the cardinality of insert a s equals |s| + 1.
mul_comm
Multiplication in a commutative structure is commutative (a * b = b * a).
Finset.sum_add_distrib
Summing a sum of two functions over a finset equals the sum of their individual sums.
connected_cubic_bipartite_has_no_cut_vertex_sum_bipartite_edges
The sum over A1 of degrees into B1 equals the sum over B1 of degrees into A1.
dvd_mul_right
For any elements a and b, a divides a * b.
Finset.card_le_card
If a finset s is a subset of t, then |s| ≤ |t|.
Finset.mem_coe
An element belongs to the set coercion of a finset if and only if it belongs to the finset.
connected_cubic_bipartite_has_no_cut_vertex_exists_adj_of_connected
In a connected graph, if u ∈ S and w ∉ S, there exist a ∈ S and b ∉ S that are adjacent.
Finset.card_pos
A finset has strictly positive cardinality if and only if it is non-empty.
Finset.eq_of_subset_of_card_le
If s ⊆ t and |t| ≤ |s|, then s = t.
le_rfl
Every element in a preorder is less than or equal to itself (reflexivity of ≤).
Set.mem_insert
An element x always belongs to the set insert x s.

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

private lemma connected_cubic_bipartite_has_no_cut_vertex_fin2_eq_of_ne_of_ne {a b c : Fin 2}    (h1 : a ≠ c) (h2 : b ≠ c) : a = b := by  revert a b c  decideprivate lemma connected_cubic_bipartite_has_no_cut_vertex_exists_adj_of_connected    {V : Type*} (G : SimpleGraph V) (hconn : G.Connected)    (S : Set V) {u : V} (hu : u ∈ S) {w : V} (hw : w ∉ S) :    ∃ a ∈ S, ∃ b ∉ S, G.Adj a b := by  obtain ⟨p⟩ := hconn.preconnected u w  obtain ⟨d, _, h1, h2⟩ := p.exists_boundary_dart S hu hw  exact ⟨d.toProd.1, h1, d.toProd.2, h2, d.adj⟩private lemma connected_cubic_bipartite_has_no_cut_vertex_sum_bipartite_edges    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]    (A1 B1 : Finset V) :    ∑ u ∈ A1, (B1.filter (G.Adj u)).card = ∑ w ∈ B1, (A1.filter (G.Adj w)).card := by  have h1 : ∀ u, (B1.filter (G.Adj u)).card = ∑ w ∈ B1, (if G.Adj u w then 1 else 0) := by    intro u    rw [Finset.card_filter]  have h2 : ∀ w, (A1.filter (G.Adj w)).card = ∑ u ∈ A1, (if G.Adj u w then 1 else 0) := by    intro w    rw [Finset.card_filter]    apply Finset.sum_congr rfl    intro u _    by_cases h : G.Adj u w    · rw [if_pos h, if_pos (G.adj_symm h)]    · rw [if_neg h, if_neg (fun h' => h (G.adj_symm h'))]  simp_rw [h1, h2]  exact Finset.sum_comm/-- Every connected cubic bipartite graph has no cut vertex: deleting any single vertex leaves a preconnected induced subgraph. -/theorem connected_cubic_bipartite_has_no_cut_vertex    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]    (hconn : G.Connected) (hreg : G.IsRegularOfDegree 3) (hbip : G.IsBipartite)    (v : V) : (G.induce {v}ᶜ).Preconnected := by  classical  rw [SimpleGraph.Preconnected]  by_contra! hnot  obtain ⟨x, y, hxy⟩ := hnot  obtain ⟨c⟩ := hbip  let H := G.induce {v}ᶜ  let C1 : Finset V := Finset.univ.filter (fun u => ∃ h : u ∈ ({v}ᶜ : Set V), H.Reachable x ⟨u, h⟩)  have hC1_eq : C1 = Finset.univ.filter (fun u => ∃ h : u ∈ ({v}ᶜ : Set V), H.Reachable x ⟨u, h⟩) := rfl  have hx : x.1 ∈ C1 := by    rw [hC1_eq, Finset.mem_filter]    refine ⟨Finset.mem_univ _, x.2, ?_⟩    have : (⟨x.1, x.2⟩ : {w : V // w ∈ ({v}ᶜ : Set V)}) = x := Subtype.ext rfl    rw [this]  have hy : y.1 ∉ C1 := by    rw [hC1_eq, Finset.mem_filter]    rintro ⟨-, h, hr⟩    have : (⟨y.1, h⟩ : {w : V // w ∈ ({v}ᶜ : Set V)}) = y := Subtype.ext rfl    rw [this] at hr    exact hxy hr  have hv : v ∉ C1 := by    rw [hC1_eq, Finset.mem_filter]    rintro ⟨-, h, -⟩    exact h rfl  have hadj : ∀ {u w}, u ∈ C1 → G.Adj u w → w ∈ C1 ∨ w = v := by    intro u w hu hadj    by_cases hw : w = v    · exact Or.inr hw    · left      rw [hC1_eq, Finset.mem_filter] at hu ⊢      obtain ⟨-, hu_ne, hr⟩ := hu      have hw_mem : w ∈ ({v}ᶜ : Set V) := hw      refine ⟨Finset.mem_univ _, hw_mem, ?_⟩      have hadjH : H.Adj ⟨u, hu_ne⟩ ⟨w, hw_mem⟩ := by        rw [SimpleGraph.induce_adj]        exact hadj      exact hr.trans hadjH.reachable  let A1 := C1.filter (fun u => c u = c v)  let B1 := C1.filter (fun u => c u ≠ c v)  have hB1_eq : B1 = C1.filter (fun u => c u ≠ c v) := rfl  have h_A1_deg : ∀ u ∈ A1, (B1.filter (G.Adj u)).card = 3 := by    intro u hu    rw [Finset.mem_filter] at hu    have hsub : ∀ w, G.Adj u w → w ∈ B1 := by      intro w hw      have hc : c u ≠ c w := (c.map_rel hw).ne      have hcases := hadj hu.1 hw      rw [Finset.mem_filter]      obtain hw_c1 | rfl := hcases      · refine ⟨hw_c1, ?_⟩        intro hcw        rw [hu.2, hcw] at hc        exact hc rfl      · exfalso        exact hc hu.2    have h_eq : B1.filter (G.Adj u) = G.neighborFinset u := by      ext w      simp only [Finset.mem_filter, SimpleGraph.mem_neighborFinset]      constructor      · rintro ⟨-, hw⟩; exact hw      · intro hw; exact ⟨hsub w hw, hw⟩    have hd : (B1.filter (G.Adj u)).card = G.degree u := congr_arg Finset.card h_eq    rw [hd, hreg u]  have h_B1_deg : ∀ w ∈ B1, (A1.filter (G.Adj w)).card + (if G.Adj w v then 1 else 0) = 3 := by    intro w hw    rw [Finset.mem_filter] at hw    have hvA1 : v ∉ A1 := fun h => hv (Finset.mem_filter.mp h).1    have hsub : ∀ z, G.Adj w z → z ∈ A1 ∨ z = v := by      intro z hz      have hc : c z ≠ c w := (c.map_rel hz).symm.ne      have hcases := hadj hw.1 hz      obtain hz_c1 | rfl := hcases      · left        rw [Finset.mem_filter]        refine ⟨hz_c1, ?_⟩        exact connected_cubic_bipartite_has_no_cut_vertex_fin2_eq_of_ne_of_ne hc hw.2.symm      · right        rfl    by_cases hadjv : G.Adj w v    · simp only [hadjv, ite_true]      have h_eq : G.neighborFinset w = insert v (A1.filter (G.Adj w)) := by        ext z        simp only [SimpleGraph.mem_neighborFinset, Finset.mem_insert, Finset.mem_filter]        constructor        · intro hz          obtain hz' | rfl := hsub z hz          · exact Or.inr ⟨hz', hz⟩          · exact Or.inl rfl        · rintro (rfl | ⟨-, hz⟩)          · exact hadjv          · exact hz      have hv_not_mem : v ∉ A1.filter (G.Adj w) := by        simp [hvA1]      have hd : G.degree w = (insert v (A1.filter (G.Adj w))).card := congr_arg Finset.card h_eq      rw [Finset.card_insert_of_notMem hv_not_mem] at hd      have := hreg w      omega    · simp only [hadjv, ite_false, add_zero]      have h_eq : G.neighborFinset w = A1.filter (G.Adj w) := by        ext z        simp only [SimpleGraph.mem_neighborFinset, Finset.mem_filter]        constructor        · intro hz          obtain hz' | rfl := hsub z hz          · exact ⟨hz', hz⟩          · exact (hadjv hz).elim        · rintro ⟨-, hz⟩          exact hz      have hd : G.degree w = (A1.filter (G.Adj w)).card := congr_arg Finset.card h_eq      rw [← hd, hreg w]  have h_sum_A1 : ∑ u ∈ A1, (B1.filter (G.Adj u)).card = 3 * A1.card := by    have : ∑ u ∈ A1, (B1.filter (G.Adj u)).card = ∑ u ∈ A1, 3 := Finset.sum_congr rfl h_A1_deg    rw [this]    simp [mul_comm]  have h_sum_B1 : (∑ w ∈ B1, (A1.filter (G.Adj w)).card) + (B1.filter (fun w => G.Adj w v)).card = 3 * B1.card := by    have h_card : (B1.filter (fun w => G.Adj w v)).card = ∑ w ∈ B1, (if G.Adj w v then 1 else 0) := by      rw [Finset.card_filter]    rw [h_card, ← Finset.sum_add_distrib]    have : ∑ w ∈ B1, ((A1.filter (G.Adj w)).card + (if G.Adj w v then 1 else 0)) = ∑ w ∈ B1, 3 :=      Finset.sum_congr rfl h_B1_deg    rw [this]    simp [mul_comm]  have h_filter_eq : B1.filter (fun w => G.Adj w v) = C1.filter (fun w => G.Adj w v) := by    rw [hB1_eq]    ext w    simp only [Finset.mem_filter]    constructor    · rintro ⟨⟨hw, -⟩, hadj'⟩      exact ⟨hw, hadj'⟩    · rintro ⟨hw, hadj'⟩      have hc : c w ≠ c v := (c.map_rel hadj').ne      exact ⟨⟨hw, hc⟩, hadj'⟩  let k := (C1.filter (fun w => G.Adj w v)).card  have hdvd : 3 ∣ k := by    have h_edges := connected_cubic_bipartite_has_no_cut_vertex_sum_bipartite_edges G A1 B1    have hk_eq : k = (B1.filter (fun w => G.Adj w v)).card := h_filter_eq.symm ▸ rfl    have h_eq : 3 * A1.card + k = 3 * B1.card := by      rw [hk_eq, ← h_sum_A1, h_edges, h_sum_B1]    have : k = 3 * (B1.card - A1.card) := by omega    rw [this]    exact dvd_mul_right 3 (B1.card - A1.card)  have hk_sub : C1.filter (fun w => G.Adj w v) ⊆ G.neighborFinset v := by    intro w hw    rw [Finset.mem_filter] at hw    rw [SimpleGraph.mem_neighborFinset]    exact hw.2.symm  have hdeg : G.degree v = 3 := hreg v  have hk_le : k ≤ 3 := by    have := Finset.card_le_card hk_sub    rw [← hdeg]    exact this  have hk_ne_zero : k ≠ 0 := by    intro hk0    have hv' : (v : V) ∉ (C1 : Set V) := fun h => hv (Finset.mem_coe.mp h)    obtain ⟨a, ha, b, hb, hab⟩ := connected_cubic_bipartite_has_no_cut_vertex_exists_adj_of_connected G hconn (C1 : Set V) (Finset.mem_coe.mpr hx) hv'    rw [Finset.mem_coe] at ha hb    have hcases := hadj ha hab    obtain hb_c1 | hb_v := hcases    · exact hb hb_c1    · rw [hb_v] at hab      have ha_mem : a ∈ C1.filter (fun w => G.Adj w v) := by        rw [Finset.mem_filter]        exact ⟨ha, hab⟩      have : 0 < (C1.filter (fun w => G.Adj w v)).card := Finset.card_pos.mpr ⟨a, ha_mem⟩      omega  have hk_ne_three : k ≠ 3 := by    intro hk3    have h_eq : C1.filter (fun w => G.Adj w v) = G.neighborFinset v := by      apply Finset.eq_of_subset_of_card_le hk_sub      change (G.neighborFinset v).card ≤ k      rw [hk3, ← hdeg]      exact le_rfl    have h_neigh_sub : ∀ w, G.Adj v w → w ∈ C1 := by      intro w hw      have : w ∈ G.neighborFinset v := by        rw [SimpleGraph.mem_neighborFinset]        exact hw      rw [← h_eq, Finset.mem_filter] at this      exact this.1    let S : Set V := insert v (C1 : Set V)    have hy_not_S : y.1 ∉ S := by      intro hyS      cases hyS with      | inl h => exact y.2 h      | inr h => exact hy (Finset.mem_coe.mp h)    obtain ⟨a, ha, b, hb, hab⟩ := connected_cubic_bipartite_has_no_cut_vertex_exists_adj_of_connected G hconn S (Set.mem_insert v (C1 : Set V)) hy_not_S    cases ha with    | inl ha_v =>      subst ha_v      exact hb (Or.inr (Finset.mem_coe.mpr (h_neigh_sub b hab)))    | inr ha_c1 =>      rw [Finset.mem_coe] at ha_c1      have hcases := hadj ha_c1 hab      obtain hb_c1 | hb_v := hcases      · exact hb (Or.inr (Finset.mem_coe.mpr hb_c1))      · apply hb        rw [hb_v]        exact Or.inl rfl  obtain ⟨m, hm⟩ := hdvd  omega
See it in the graphDiscuss this resultChallenge it