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.^[1]

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.

In coordinate form, the kernel equation says that for every vertex v, the sum of the coordinates assigned to its neighbors equals zero. Because each coordinate is nonzero, this balancing relation covers the entire graph. The property arises in spectral graph theory and chemical graph theory, where adjacency nullity and full-support zero modes can model molecular graph phenomena. It has also motivated enumeration, construction, regularity, symmetry, and physical-network realization problems.^[2]

The locked identity is: finite simple graph + singular adjacency matrix + one-dimensional nullspace + generator with nonzero entry at every vertex -> a globally supported unique zero-eigenvalue relation, defining a nut graph.

Structural Signature¶

the finite simple graph G — undirected, loopless, and without parallel edges in the standard definition;
the vertex set — has order at least two;
the adjacency matrix A(G) — symmetric zero-one matrix determined by adjacency;
singularity — det A(G)=0, so a nonzero kernel vector exists;
nullity one — dim ker A(G)=1, equivalently zero has multiplicity one for the symmetric adjacency matrix;
the kernel generator x — any nonzero solution of A(G)x=0 spans the kernel;
full support — x_v≠0 for every vertex v;
neighbor-sum equation — Σ_{u~v} x_u=0 at every vertex;
scale invariance — multiplying x by a nonzero scalar does not change the property;
label invariance — graph relabeling permutes coordinates and preserves nut status;
global core — in core/periphery terminology, all vertices belong to the zero-mode core and the periphery is empty;
recognition test — compute rank/nullity and inspect the support of a kernel basis vector;
construction closure questions — graph operations are studied for whether they preserve both conditions.

The definition uses the adjacency matrix. A graph can have a one-dimensional kernel for another matrix, such as its Laplacian, without being a nut graph.

What It Is Not¶

Not any singular graph. Singularity permits any positive nullity and kernel support.
Not any nullity-one graph. The unique kernel vector must be nonzero at every vertex.
Not a graph with matrix rank one. The adjacency matrix has corank one, not rank one.
Not defined by Laplacian nullity. Every connected graph has Laplacian nullity one; that would trivialize the class.
Not necessarily regular, planar, chemical, or polyhedral. Those are studied subclasses.
Not a graph with a “nut-shaped” drawing. The name is technical.
Not the graph-theoretic nullity of a cycle space. Here nullity means adjacency-matrix kernel dimension.
Not a zero-eigenvalue statement alone. Multiplicity and full support are indispensable.

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. These existence facts are consequences, not definition components.

Chemical nut graphs add degree restrictions motivated by molecular valence. Their physical interpretation depends on a chosen molecular-orbital or conduction model; mathematical nut status alone does not guarantee a realizable stable molecule or a particular measured property.

Directed generalizations require care because an adjacency matrix need not be symmetric. Left and right kernels can differ, producing dextro-, laevo-, bi-, or ambi-nut definitions. Those are recognized variants, not exact synonyms of the undirected node.

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.

The neighbor-sum form is often the easiest manual diagnostic: each row of A x=0 says the sum over neighbor coordinates vanishes. A leaf would force its sole neighbor's coordinate to zero, violating fullness; this helps explain why nut graphs have no leaves. Bipartite structure and other consequences require proofs from the spectral conditions, not intuition from the name.

The nearest catalog target domain_specific:kernel covers inputs mapped to zero by a linear or algebraic map. It lacks graph adjacency, nullity exactly one, full support, and the spectral/chemical graph consequences. domain_specific:hyper_wiener_index is a semantic graph-theory neighbor only. Exact coverage is absent.

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. Isomorphism classes can be generated and filtered without relying on drawings, while theoretical constructions can focus on preserving one-dimensionality and fullness separately.

Abstract Reasoning¶

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.
If dim ker A>1, even a full kernel vector does not rescue nut status because uniqueness up to scale fails.
If the unique kernel vector has a zero at vertex v, deleting or modifying v can alter singularity differently from a globally supported mode.
Graph relabeling multiplies A by permutation matrices and permutes x, preserving nullity and fullness.
Scaling x changes no neighbor-sum equation or support property.
In an undirected graph, symmetry of A makes algebraic and geometric multiplicity of zero coincide; directed variants lose that simplification.
A connected graph's Laplacian always has the all-ones vector in its kernel, which shows why substituting Laplacian for adjacency would define a different and broad class.
Coalescing known nut graphs can preserve the class under established hypotheses, illustrating that constructions must protect both corank and support.

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.

Examples¶

Sciriha graphs: the three order-seven examples establish the smallest ordinary nut graphs;
antiprism family: selected antiprism orders yield a full unique zero mode;
Frucht graph: a cubic asymmetric graph that is also a nut graph;
recognition computation: exact row reduction finds rank n−1, then a basis vector is checked for zeros;
non-example with a leaf: the leaf equation forces a zero kernel coordinate;
non-example with nullity two: full vectors may exist, but the zero eigenspace is not unique;
directed extension: right- and left-full kernel conditions generate distinct nut-digraph variants.

Structural Tensions¶

local adjacency vs. global spectrum — simple neighbor relations produce a whole-graph null mode;
singularity vs. uniqueness — zero eigenvalue is required, but exactly one dimension is allowed;
uniqueness vs. full participation — a unique relation can still omit vertices unless fullness is imposed;
mathematical class vs. chemical interpretation — spectral qualification is exact while physical meaning is model-dependent;
enumeration vs. construction — exhaustive catalogs and infinite families answer different existence questions;
undirected symmetry vs. directed variants — left/right kernel distinctions appear once symmetry is removed.

Structural–Framed Character¶

Nut Graph is fully structural. The definition is invariant under relabeling and decided by exact linear algebra. Historical naming and application domain do not affect membership.

Structural Core vs. Domain Accent¶

The core is a unique null direction whose support covers every component coordinate. The domain accent is the adjacency matrix of a finite simple graph and its vertex-neighbor interpretation. Without that accent, the object is a full-support one-dimensional kernel, not a nut graph.

Kernel — the defining vector lies in the adjacency map's nullspace.
Global Constraint — every vertex satisfies a coupled neighbor-sum equation.
Spectral Invariant — zero-eigenvalue multiplicity is preserved by graph isomorphism.
Full Support — no vertex coordinate vanishes.
Uniqueness up to Scale — the one-dimensional kernel fixes the relation modulo scalar.

The prospective DAG uses composition under domain_specific:kernel.

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

Not to Be Confused With¶

singular graph generally;
adjacency nullity one without full support;
matrix rank one;
Laplacian nullity;
cycle-space nullity;
core graph of higher nullity;
chemical nut graph as the entire class;
directed nut variants as exact synonyms.

References¶

[1] Irene Sciriha and Ivan Gutman, “Nut Graphs: Maximally Extending Cores,” Utilitas Mathematica 54, 1998, 257–272. registry ↩

[2] Patrick W. Fowler, Tomaž Pisanski, and Irene Sciriha, “Existence of Regular Nut Graphs and the Fowler Construction,” Journal of Mathematical Chemistry 58, 2020, 271–294. registry ↩

[3] Kris Coolsaet, Patrick W. Fowler, and Jan Goedgebeur, “Generation and Properties of Nut Graphs,” MATCH Communications in Mathematical and in Computer Chemistry 80, 2018, 423–444, https://caagt.ugent.be/jgoedgeb/paper-nutgraphs.pdf. registry

[4] “Nut graph,” Wikipedia, frozen evidence packet, https://en.wikipedia.org/wiki/Nut_graph. registry