simple_graph_diam_two_nut_graph_card_ge_four
Every finite simple nut graph of diameter 2 has at least 4 vertices.
Statement
theorem simple_graph_diam_two_nut_graph_card_ge_four {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hnut : simple_graph_is_nut_graph G) (hdiam : G.diam = 2) : 4 ≤ Fintype.card V
- Source
- step towards op_1267_diameter_two_nut_graph_has_binary_vector
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- simple_graph_is_nut_graphA finite simple graph G is a nut graph if its adjacency matrix over ℝ has nullity 1 and every non-zero vector in the null space has a…
The proof, explained
A nut graph is a simple graph whose adjacency matrix has a 1-dimensional kernel spanned by a vector with no zero coordinates. If a nut graph of diameter 2 had fewer than 4 vertices, it would have exactly 3 vertices: two non-adjacent vertices u and v at distance 2 and an intermediate neighbor w. In that case, u and v would share identical neighborhoods, making rows u and v of the adjacency matrix equal, which places the difference vector y = e_u - e_v in the kernel. But y vanishes at w, contradicting the nut graph requirement that non-zero kernel vectors have nowhere-vanishing coordinates.
There exist two vertices u, v at distance 2 and a walk p of length 2 between them.
Since G has diameter 2, its diameter is non-zero, so V contains at least two vertices. A nonempty graph contains a pair of vertices u, v whose distance equals the diameter, which is 2. Because dist(u, v) = 2 ≠ 0, u and v are connected by a walk p whose length equals their distance, namely 2.
uses
SimpleGraph.nontrivial_of_diam_ne_zero,SimpleGraph.exists_dist_eq_diam,SimpleGraph.Reachable.of_dist_ne_zerohave hne : G.diam ≠ 0 := by omega have hnt : Nontrivial V := SimpleGraph.nontrivial_of_diam_ne_zero hne obtain ⟨u, v, huv⟩ := SimpleGraph.exists_dist_eq_diam (G := G) rw [hdiam] at huv have hreach : G.Reachable u v := SimpleGraph.Reachable.of_dist_ne_zero (by omega) obtain ⟨p, hp⟩ := hreach.exists_walk_length_eq_dist have hplen : p.length = 2 := by rw [hp, huv]
The midpoint w of the walk p is adjacent to both u and v.
Let w be the middle vertex p(1) along the walk p of length 2. Because consecutive vertices on a walk are adjacent, the start vertex p(0) = u is adjacent to w, and w is adjacent to the end vertex p(2) = v. By symmetry of adjacency, v is also adjacent to w.
uses
SimpleGraph.Walk.adj_getVert_succ,SimpleGraph.Walk.getVert_zero,SimpleGraph.Walk.getVert_length,SimpleGraph.adj_commset w : V := p.getVert 1 with hwdef have huw : G.Adj u w := by have h := SimpleGraph.Walk.adj_getVert_succ p (i := 0) (by omega) simpa [w, SimpleGraph.Walk.getVert_zero] using h have hwv : G.Adj w v := by have h := SimpleGraph.Walk.adj_getVert_succ p (i := 1) (by omega) have h2 : p.getVert 2 = v := by have := SimpleGraph.Walk.getVert_length p rwa [hplen] at this simpa [w, h2] using h have hwv' : G.Adj v w := (SimpleGraph.adj_comm G w v).mp hwv
Vertices u and v are not adjacent, and the vertices u, w, v are pairwise distinct.
Vertices u and v cannot be adjacent because their distance is 2, not 1. Since simple graphs have no self-loops, the adjacencies u ~ w and w ~ v imply u ≠ w and w ≠ v. Finally, u ≠ v because the distance between identical vertices is 0, whereas dist(u, v) = 2.
uses
SimpleGraph.dist_eq_one_iff_adj,SimpleGraph.adj_comm,SimpleGraph.dist_selfhave hnotadj : ¬ G.Adj u v := by rw [← SimpleGraph.dist_eq_one_iff_adj] omega have hnotadj' : ¬ G.Adj v u := fun h => hnotadj ((SimpleGraph.adj_comm G v u).mp h) have huw_ne : u ≠ w := huw.ne have hwv_ne : w ≠ v := hwv.ne have huv_ne : u ≠ v := by rintro rfl rw [SimpleGraph.dist_self] at huv omega
The subset {u, w, v} has cardinality 3, hence |V| ≥ 3.
Because u, w, and v are pairwise distinct, the set {u, w, v} has exactly 3 elements. Since it is a subset of the entire vertex set V, the total number of vertices |V| is at least 3.
uses
Finset.card_insert_of_notMem,Finset.card_singleton,Finset.mem_singleton,Finset.mem_insert,Finset.card_le_card,Finset.subset_univ,Finset.card_univhave hcard3 : ({u, w, v} : Finset V).card = 3 := by rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton] · simp only [Finset.mem_singleton]; exact hwv_ne · simp only [Finset.mem_insert, Finset.mem_singleton] exact fun h => h.elim huw_ne huv_ne have hge3 : 3 ≤ Fintype.card V := by have h := Finset.card_le_card (Finset.subset_univ ({u, w, v} : Finset V)) rw [Finset.card_univ] at h omega
If |V| < 4, then |V| = 3 and every vertex of G is in {u, w, v}.
Assuming for contradiction that |V| < 4, the bounds 3 ≤ |V| < 4 force |V| = 3. A 3-element subset of a 3-element set must be the entire set, so {u, w, v} is all of V. Thus every vertex x ∈ V is equal to u, w, or v.
uses
not_le,Finset.eq_univ_of_card,Finset.mem_univ,Finset.mem_insert,Finset.mem_singletonby_contra hcon simp only [not_le] at hcon have hcard : Fintype.card V = 3 := by omega have huniv : ({u, w, v} : Finset V) = Finset.univ := Finset.eq_univ_of_card _ (by rw [hcard3, hcard]) have hmem3 : ∀ x : V, x = u ∨ x = w ∨ x = v := by intro x have hx : x ∈ ({u, w, v} : Finset V) := by rw [huniv]; exact Finset.mem_univ x simp only [Finset.mem_insert, Finset.mem_singleton] at hx tauto
Vertices u and v have identical neighborhoods: for every x ∈ V, u ~ x if and only if v ~ x.
We test all three possible values for x: when x = u, neither u ~ u nor v ~ u holds; when x = w, both u ~ w and v ~ w hold; when x = v, neither u ~ v nor v ~ v holds. In all cases, u ~ x is equivalent to v ~ x.
uses
SimpleGraph.irreflhave hAdj : ∀ x : V, G.Adj u x ↔ G.Adj v x := by intro x rcases hmem3 x with rfl | rfl | rfl · exact ⟨fun h => absurd h (SimpleGraph.irrefl G), fun h => absurd h hnotadj'⟩ · exact ⟨fun _ => hwv', fun _ => huw⟩ · exact ⟨fun h => absurd h hnotadj, fun h => absurd h (SimpleGraph.irrefl G)⟩
The rows of the adjacency matrix corresponding to u and v are identical, and the matrix is symmetric.
Each entry of the adjacency matrix is 1 for an edge and 0 otherwise. Since u and v have identical neighbors, rows u and v match across all columns. Furthermore, adjacency is symmetric, so the adjacency matrix is symmetric.
uses
SimpleGraph.adjMatrix_apply,if_pos,if_neg,SimpleGraph.adj_commhave hrow : ∀ x : V, (SimpleGraph.adjMatrix ℝ G) u x = (SimpleGraph.adjMatrix ℝ G) v x := by intro x simp only [SimpleGraph.adjMatrix_apply] by_cases h : G.Adj u x · rw [if_pos h, if_pos ((hAdj x).mp h)] · rw [if_neg h, if_neg (fun hh => h ((hAdj x).mpr hh))] have hsymm : ∀ a b : V, (SimpleGraph.adjMatrix ℝ G) a b = (SimpleGraph.adjMatrix ℝ G) b a := by intro a b simp only [SimpleGraph.adjMatrix_apply] by_cases h : G.Adj a b · rw [if_pos h, if_pos ((SimpleGraph.adj_comm G a b).mp h)] · rw [if_neg h, if_neg (fun hh => h ((SimpleGraph.adj_comm G a b).mpr hh))]
The vector y = e_u - e_v belongs to the kernel of the adjacency matrix.
Multiplying the adjacency matrix A by y = e_u - e_v yields col_u(A) - col_v(A). By symmetry of A, these columns equal the corresponding rows, row_u(A) - row_v(A), which cancel to zero since rows u and v are identical. Thus A y = 0.
uses
LinearMap.mem_ker,Matrix.toLin'_apply,Matrix.mulVec_sub,Matrix.mulVec_single_one,Pi.sub_apply,Matrix.col_apply,Pi.zero_apply,sub_eq_zero.mprset y : V → ℝ := Pi.single u (1:ℝ) - Pi.single v (1:ℝ) with hydef have hmem : y ∈ (Matrix.toLin' (SimpleGraph.adjMatrix ℝ G)).ker := by rw [LinearMap.mem_ker, Matrix.toLin'_apply, hydef, Matrix.mulVec_sub, Matrix.mulVec_single_one, Matrix.mulVec_single_one] funext x simp only [Pi.sub_apply, Matrix.col_apply, Pi.zero_apply] rw [hsymm x u, hsymm x v] exact sub_eq_zero.mpr (hrow x)
The vector y contradicts the nut graph condition, completing the proof.
Evaluating y at u gives y(u) = 1 - 0 = 1 ≠ 0, so y is a non-zero vector. But evaluating y at the midpoint w gives y(w) = 0 - 0 = 0. By the definition of a nut graph, every non-zero vector in the kernel of the adjacency matrix must have strictly non-zero coordinates at all vertices, so y(w) cannot be 0. This contradiction shows that |V| ≥ 4.
uses
Pi.single_eq_same,Pi.single_eq_of_ne,Ne.symmhave hyne : y ≠ 0 := by intro h have h1 : y u = (0 : V → ℝ) u := by rw [h] simp [hydef, Pi.single_eq_same, Pi.single_eq_of_ne huv_ne] at h1 have hzero : y w = 0 := by simp [hydef, Pi.single_eq_of_ne (Ne.symm huw_ne), Pi.single_eq_of_ne hwv_ne] exact (hnut.2 y hmem hyne w) hzero
Finset.eq_univ_of_card- If a finite subset of a finite type has cardinality equal to the type, it is the universal set.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to {a} if and only if it equals a.
Finset.mem_univ- Every element of a finite type belongs to its universal set.
Finset.card_insert_of_notMem- Inserting an element not in a finite set increases its cardinality by 1.
Finset.card_le_card- A subset of a finite set has cardinality less than or equal to the superset.
Finset.card_singleton- The cardinality of a singleton set is 1.
Finset.card_univ- The cardinality of the universal set of a finite type equals the cardinality of the type.
Finset.subset_univ- Every finite set is a subset of the universal set.
LinearMap.mem_ker- A vector is in the kernel of a linear map if and only if the map sends it to zero.
Matrix.col_apply- The j-th component of the i-th column of a matrix A is the entry A_{j, i}.
Matrix.mulVec_single_one- Multiplying a matrix by the standard basis vector e_j yields its j-th column.
Matrix.mulVec_sub- Matrix-vector multiplication distributes over vector subtraction: A(x - y) = Ax - Ay.
Matrix.toLin'_apply- Applying the linear map of a matrix to a vector is matrix-vector multiplication.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
Pi.single_eq_same- The standard basis vector e_i evaluated at i equals the given scalar.
Pi.single_eq_of_ne- The standard basis vector e_i evaluated at any index other than i equals 0.
Pi.sub_apply- Function subtraction is defined pointwise: (f - g)(i) = f(i) - g(i).
Pi.zero_apply- The zero function evaluates to 0 everywhere.
SimpleGraph.adj_comm- Adjacency in a simple graph is symmetric: u is adjacent to v if and only if v is adjacent to u.
SimpleGraph.adjMatrix_apply- The (v, w) entry of the adjacency matrix is 1 if v and w are adjacent, and 0 otherwise.
SimpleGraph.dist_eq_one_iff_adj- Two vertices are adjacent if and only if the distance between them is 1.
SimpleGraph.dist_self- The distance from any vertex to itself is 0.
SimpleGraph.exists_dist_eq_diam- In a nonempty graph, there exist two vertices whose distance equals the diameter of the graph.
SimpleGraph.irrefl- A simple graph has no self-loops: no vertex is adjacent to itself.
SimpleGraph.nontrivial_of_diam_ne_zero- A graph with non-zero diameter has at least two vertices.
SimpleGraph.Reachable.of_dist_ne_zero- If the distance between two vertices is non-zero, there is a walk connecting them.
SimpleGraph.Walk.adj_getVert_succ- Consecutive vertices along a walk in a graph are adjacent.
SimpleGraph.Walk.getVert_length- The vertex at index equal to the length of a walk from u to v is v.
SimpleGraph.Walk.getVert_zero- The vertex at index 0 of a walk from u to v is u.
if_neg- If a condition is false, the corresponding if-then-else expression evaluates to the 'else' branch.
if_pos- If a condition is true, the corresponding if-then-else expression evaluates to the 'then' branch.
not_le- For linear orders, ¬(a ≤ b) is equivalent to b < a.
sub_eq_zero.mpr- If two elements are equal, their difference is zero.
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.
/-- Every finite simple nut graph of diameter 2 has at least 4 vertices. -/theorem simple_graph_diam_two_nut_graph_card_ge_four {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hnut : simple_graph_is_nut_graph G) (hdiam : G.diam = 2) : 4 ≤ Fintype.card V := by have hne : G.diam ≠ 0 := by omega have hnt : Nontrivial V := SimpleGraph.nontrivial_of_diam_ne_zero hne obtain ⟨u, v, huv⟩ := SimpleGraph.exists_dist_eq_diam (G := G) rw [hdiam] at huv have hreach : G.Reachable u v := SimpleGraph.Reachable.of_dist_ne_zero (by omega) obtain ⟨p, hp⟩ := hreach.exists_walk_length_eq_dist have hplen : p.length = 2 := by rw [hp, huv] set w : V := p.getVert 1 with hwdef have huw : G.Adj u w := by have h := SimpleGraph.Walk.adj_getVert_succ p (i := 0) (by omega) simpa [w, SimpleGraph.Walk.getVert_zero] using h have hwv : G.Adj w v := by have h := SimpleGraph.Walk.adj_getVert_succ p (i := 1) (by omega) have h2 : p.getVert 2 = v := by have := SimpleGraph.Walk.getVert_length p rwa [hplen] at this simpa [w, h2] using h have hwv' : G.Adj v w := (SimpleGraph.adj_comm G w v).mp hwv have hnotadj : ¬ G.Adj u v := by rw [← SimpleGraph.dist_eq_one_iff_adj] omega have hnotadj' : ¬ G.Adj v u := fun h => hnotadj ((SimpleGraph.adj_comm G v u).mp h) have huw_ne : u ≠ w := huw.ne have hwv_ne : w ≠ v := hwv.ne have huv_ne : u ≠ v := by rintro rfl rw [SimpleGraph.dist_self] at huv omega have hcard3 : ({u, w, v} : Finset V).card = 3 := by rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton] · simp only [Finset.mem_singleton]; exact hwv_ne · simp only [Finset.mem_insert, Finset.mem_singleton] exact fun h => h.elim huw_ne huv_ne have hge3 : 3 ≤ Fintype.card V := by have h := Finset.card_le_card (Finset.subset_univ ({u, w, v} : Finset V)) rw [Finset.card_univ] at h omega by_contra hcon simp only [not_le] at hcon have hcard : Fintype.card V = 3 := by omega have huniv : ({u, w, v} : Finset V) = Finset.univ := Finset.eq_univ_of_card _ (by rw [hcard3, hcard]) have hmem3 : ∀ x : V, x = u ∨ x = w ∨ x = v := by intro x have hx : x ∈ ({u, w, v} : Finset V) := by rw [huniv]; exact Finset.mem_univ x simp only [Finset.mem_insert, Finset.mem_singleton] at hx tauto have hAdj : ∀ x : V, G.Adj u x ↔ G.Adj v x := by intro x rcases hmem3 x with rfl | rfl | rfl · exact ⟨fun h => absurd h (SimpleGraph.irrefl G), fun h => absurd h hnotadj'⟩ · exact ⟨fun _ => hwv', fun _ => huw⟩ · exact ⟨fun h => absurd h hnotadj, fun h => absurd h (SimpleGraph.irrefl G)⟩ have hrow : ∀ x : V, (SimpleGraph.adjMatrix ℝ G) u x = (SimpleGraph.adjMatrix ℝ G) v x := by intro x simp only [SimpleGraph.adjMatrix_apply] by_cases h : G.Adj u x · rw [if_pos h, if_pos ((hAdj x).mp h)] · rw [if_neg h, if_neg (fun hh => h ((hAdj x).mpr hh))] have hsymm : ∀ a b : V, (SimpleGraph.adjMatrix ℝ G) a b = (SimpleGraph.adjMatrix ℝ G) b a := by intro a b simp only [SimpleGraph.adjMatrix_apply] by_cases h : G.Adj a b · rw [if_pos h, if_pos ((SimpleGraph.adj_comm G a b).mp h)] · rw [if_neg h, if_neg (fun hh => h ((SimpleGraph.adj_comm G a b).mpr hh))] set y : V → ℝ := Pi.single u (1:ℝ) - Pi.single v (1:ℝ) with hydef have hmem : y ∈ (Matrix.toLin' (SimpleGraph.adjMatrix ℝ G)).ker := by rw [LinearMap.mem_ker, Matrix.toLin'_apply, hydef, Matrix.mulVec_sub, Matrix.mulVec_single_one, Matrix.mulVec_single_one] funext x simp only [Pi.sub_apply, Matrix.col_apply, Pi.zero_apply] rw [hsymm x u, hsymm x v] exact sub_eq_zero.mpr (hrow x) have hyne : y ≠ 0 := by intro h have h1 : y u = (0 : V → ℝ) u := by rw [h] simp [hydef, Pi.single_eq_same, Pi.single_eq_of_ne huv_ne] at h1 have hzero : y w = 0 := by simp [hydef, Pi.single_eq_of_ne (Ne.symm huw_ne), Pi.single_eq_of_ne hwv_ne] exact (hnut.2 y hmem hyne w) hzero