Nut Graph

A finite simple graph whose adjacency matrix has a one-dimensional kernel generated by a vector nonzero at every vertex, making zero a simple eigenvalue with full vertex support.

Version

v1 · 2026-08-30 · History

Domain-specific #

2404

Origin domain

mathematics

Subdomain

spectral graph theory

Aliases

Adjacency nut graph, Nullity-one full-core graph

Core Idea

A Nut Graph is a finite simple graph G with at least two vertices whose adjacency matrix A(G) has nullity exactly one and whose nonzero kernel vector has no zero coordinate. Equivalently, zero is an adjacency eigenvalue of multiplicity one and its eigenspace is generated by a full vector: every vertex participates in the unique linear dependence A x = 0.

The two conditions do separate work. Nullity one makes the zero-eigenspace unique up to scalar multiplication. Full support makes every coordinate essential: no vertex lies outside the support of the kernel relation. A singular graph with larger nullity is not a nut graph; a nullity-one graph whose unique kernel vector vanishes at even one vertex is not a nut graph.

Scope of Application

Nut graphs are studied in spectral and algebraic graph theory, graph enumeration, mathematical chemistry, molecular conduction models, and physical graph-network experiments. Researchers ask which orders and degrees admit nut graphs, enumerate nonisomorphic instances under chemical degree restrictions, construct larger examples from smaller ones, classify symmetric or vertex-transitive examples, and extend the notion to signed or directed graphs.

For ordinary finite simple graphs, examples exist for every order at least seven, with three smallest examples at order seven. Named graph families yield conditions: certain antiprism graphs are nuts, and familiar regular graphs such as the Frucht graph provide examples.

Clarity

For an n×n adjacency matrix, nullity one means rank n−1. It does not mean rank one. A full kernel vector is a vector with no coordinate equal to zero; it need not have equal entries or equal signs. Because the kernel is one-dimensional, if one nonzero generator is full, every nonzero generator is full.

Manages Complexity

The definition condenses a global spectral condition into two computable tests. Rather than cataloging all linear dependencies among adjacency rows, one computes a nullspace dimension and checks a single basis vector's support. This creates a crisp filter for enumeration and construction.

The kernel vector also provides a shared certificate. Numerical or symbolic software can return x; every coordinate and neighbor-sum equation can be inspected.

Abstract Reasoning

1. If a graph has a leaf v with neighbor u, the equation at v forces x_u=0, so the graph cannot be a nut. 2. If dim ker A>1, even a full kernel vector does not rescue nut status because uniqueness up to scale fails. 3. If the unique kernel vector has a zero at vertex v, deleting or modifying v can alter singularity differently from a globally supported mode.

Knowledge Transfer

The exact abstraction transfers across pure, chemical, and physical-network graph settings because adjacency matrix, nullity, and full kernel vector remain literal. Degree restrictions or interpretations define subclasses.

Outside graph theory, a one-dimensional fully supported null mode can occur in other matrices, but calling it a nut graph requires a finite simple graph's adjacency matrix. The portable parents are Kernel, Spectral Analysis, Full Support, and Global Constraint.

Relationships to Other Abstractions

Current abstraction Nut Graph Domain-specific

Parents (1) — more general patterns this builds on

• Nut Graph is part of Kernel Domain-specific

  the defining vector lies in the adjacency map's nullspace.

Hierarchy paths (2) — routes to 1 parentless root

• Nut Graph → Kernel → Preimage → Function (Mapping)

Show alternative path (1)

Neighborhood in Abstraction Space

Nut Graph sits in a sparse region of the domain-specific corpus (85^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Graph Density, Distance & Planarity (11 abstractions)

Nearest neighbors

• Hosoya Index — 0.81
• Graph Sphericity — 0.81
• Knaster–Kuratowski–Mazurkiewicz Lemma — 0.80
• Strongly regular graph — 0.80
• Cubic Graph — 0.79

Computed from structural-signature embeddings · 2026-09-08