AFTD Auto-Formalizing Theoretical Domains

simple_graph_diam_two_nut_graph_card_ge_four

theoremverified

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.

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

    lines 7–13

    uses SimpleGraph.nontrivial_of_diam_ne_zero, SimpleGraph.exists_dist_eq_diam, SimpleGraph.Reachable.of_dist_ne_zero

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

    lines 14–24

    uses SimpleGraph.Walk.adj_getVert_succ, SimpleGraph.Walk.getVert_zero, SimpleGraph.Walk.getVert_length, SimpleGraph.adj_comm

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

    lines 25–34

    uses SimpleGraph.dist_eq_one_iff_adj, SimpleGraph.adj_comm, SimpleGraph.dist_self

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

    lines 35–43

    uses Finset.card_insert_of_notMem, Finset.card_singleton, Finset.mem_singleton, Finset.mem_insert, Finset.card_le_card, Finset.subset_univ, Finset.card_univ

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

    lines 44–53

    uses not_le, Finset.eq_univ_of_card, Finset.mem_univ, Finset.mem_insert, Finset.mem_singleton

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

    lines 54–59

    uses SimpleGraph.irrefl

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

    lines 60–71

    uses SimpleGraph.adjMatrix_apply, if_pos, if_neg, SimpleGraph.adj_comm

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

    lines 72–79

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

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

    lines 80–86

    uses Pi.single_eq_same, Pi.single_eq_of_ne, Ne.symm

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

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