AFTD Auto-Formalizing Theoretical Domains

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

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