simple_graph_is_nut_graph
def
A 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 non-zero entry at each vertex.
Statement
def simple_graph_is_nut_graph {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : Prop
- Defined in
- arXiv:2611.08244 Section 4
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Used by 4
- simple_graph_nut_graph_binary_vector_of_triangle_free_edgeIf a finite simple nut graph with at least 4 vertices has a triangle-free edge (an edge whose endpoints share no common neighbors), then…
- simple_graph_nut_graph_diameter_three_has_binary_vectorLet G be a finite simple nut graph on a finite vertex set. If the diameter of G is 3, then there exists a non-zero (0,1)-vector in the row…
- simple_graph_diam_two_nut_graph_card_ge_fourEvery finite simple nut graph of diameter 2 has at least 4 vertices.
- simple_graph_nut_graph_subset_neighbors_has_binary_vectorLet G be a finite simple nut graph on a vertex set V of cardinality at least 4. If there exist vertices u and v such that the neighbor set…
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. The definition simple_graph_is_nut_graph G asserts that:
1. The dimension (finrank) over ℝ of the kernel of the linear map on V → ℝ given by the adjacency matrix of G (with entries in ℝ) is equal to 1; and
2. For every vector x in the kernel of this adjacency matrix map, if x ≠ 0, then for all vertices v : V, the component x v is non-zero.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A simple graph G is a nut graph if the null space of its real adjacency matrix is 1-dimensional and contains no non-zero vector with a zero entry. -/ def simple_graph_is_nut_graph {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : Prop := Module.finrank ℝ (LinearMap.ker (Matrix.toLin' (G.adjMatrix ℝ))) = 1 ∧ ∀ x ∈ LinearMap.ker (Matrix.toLin' (G.adjMatrix ℝ)), x ≠ 0 → ∀ v : V, x v ≠ 0