connected_cubic_bipartite_has_no_cut_vertex
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
- Arena.Reachable.transReachability is transitive.
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.
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`.
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
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.
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⟩
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.
uses
Finset.card_filter,Finset.sum_congr,if_pos,if_neg,Finset.sum_commprivate 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
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.
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
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.
uses
Finset.mem_filter,Finset.mem_univ,Subtype.extlet 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
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`).
uses
Or.inr,Finset.mem_filter,Finset.mem_univ,SimpleGraph.induce_adjhave 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
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`).
uses
Finset.mem_filter,SimpleGraph.mem_neighborFinset,congr_arglet 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]
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`).
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_arghave 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]
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`).
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_righthave 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)
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`).
uses
Finset.mem_filter,SimpleGraph.mem_neighborFinset,Finset.card_le_cardhave 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
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.
uses
Finset.mem_coe,connected_cubic_bipartite_has_no_cut_vertex_exists_adj_of_connected,Finset.mem_filter,Finset.card_poshave 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
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.
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.inlhave 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
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.
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.
- The proof establishes three auxiliary private lemmas beforehand: a pigeonhole property for Fin 2, the existence of an edge crossing any non-trivial cut in a connected graph, and double-counting of bipartite edges between two finsets.
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.
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