Characteristic polynomial of a graph¶

In spectral graph theory, the characteristic polynomial of a graph is the characteristic polynomial of its adjacency matrix.

Version: v1 · 2026-09-28 · History
Domain-specific #: 8413
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Spectral Graph Theory → Mathematics

Core Idea¶

Characteristic polynomial of a graph is treated here as the recurring mathematicslogicstatistics identity summarized by this source-grounded definition: In spectral graph theory, the characteristic polynomial of a graph is the characteristic polynomial of its adjacency matrix. In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The characteristic polynomial of an endomorphism of a finite-dimensional vector space is the characteristic polynomial of the matrix of that endomorphism.

How would you explain it like I'm…

Dot-and-Line Recipe

Draw some dots and connect some of them with lines, like a map of who is friends with whom. You can write a chart that says, for every pair of dots, whether they're connected. Mathematicians turn that chart into a special number recipe called the characteristic polynomial of the graph. It stays the same no matter how you name or number the dots.

The Graph's Special Polynomial

A graph is a set of dots (vertices) joined by lines (edges). Its adjacency matrix is a grid with a 1 where two dots are connected and a 0 where they aren't. From any square grid of numbers, you can build a polynomial called its characteristic polynomial, whose zeros are special numbers of the grid called eigenvalues. The characteristic polynomial of a graph is exactly that polynomial, built from the adjacency matrix. Renumbering the dots rearranges the grid but doesn't change the polynomial.

Adjacency Characteristic Polynomial

The adjacency matrix A of a graph with n vertices is an n-by-n table whose (i, j) entry records whether vertices i and j are joined. The characteristic polynomial of any square matrix is det(xI − A), a polynomial whose roots are the matrix's eigenvalues and whose coefficients include the trace and determinant. The characteristic polynomial of the graph is simply this polynomial for A. Relabeling vertices replaces A by a similar matrix, and similar matrices share a characteristic polynomial, so it is a property of the graph itself rather than of the numbering. Its roots are the graph's spectrum, the starting point of spectral graph theory.

In spectral graph theory the characteristic polynomial of a graph G on n vertices is p_G(x) = det(xI − A), with A the adjacency matrix. It inherits the properties of matrix characteristic polynomials: it's monic of degree n, invariant under matrix similarity, has the eigenvalues as roots, and includes the trace and determinant among its coefficients. Vertex relabeling acts by permutation similarity P A Pᵀ, so p_G is a graph invariant. Its roots are the adjacency spectrum of G. Note that the definition is tied specifically to the adjacency matrix; polynomials of other graph matrices (e.g. the Laplacian) are different objects.

Scope of Application¶

Secular function and secular equationSecular function. The term secular function has been used for what is now called characteristic polynomial (in some literature the term secular function is still used).
Secular equation. In molecular orbital calculations relating to the energy of the electron and its wave function it is also used instead of the characteristic equation.
Secular function and secular equationSecular function. The term comes from the fact that the characteristic polynomial was used to calculate secular perturbations (on a time scale of a century, that is, slow compared to annual motion) of.
Secular equation. In linear algebra it is sometimes used in place of characteristic equation.
1&t-0. Another example uses hyperbolic functions of a hyperbolic angle φ.

Clarity¶

A clear use of Characteristic polynomial of a graph names the carrier, the operative relation, and the conditions under which the source treats the identity as present. The minimal definition is In spectral graph theory, the characteristic polynomial of a graph is the characteristic polynomial of its adjacency matrix.

Manages Complexity¶

Characteristic polynomial of a graph compresses multiple mathematicslogicstatistics details into a stable diagnostic relation. The source shows both the central mechanism—the characteristic polynomial of A, denoted by pA(t), is the polynomial defined by.—and the practical consequence—to prove this, one may suppose n > m, by exchanging, if needed, A and B. This compression makes cases comparable while leaving parameters, conventions, exceptions, and evidential quality explicit.

Abstract Reasoning¶

Type the carrier. Identify the mathematicslogicstatistics entities to which the claim applies.
State the relation. Use the source-grounded identity: In spectral graph theory, the characteristic polynomial of a graph is the characteristic polynomial of its adjacency matrix.
Check operation and conditions. This trace may be computed as the sum of all principal minors of A of size k.
Demand recognition evidence.

Knowledge Transfer¶

Within the home domain. Knowledge about Characteristic polynomial of a graph transfers literally when a new case preserves the same carrier type, relation, and recognition test. The term secular function has been used for what is now called characteristic polynomial (in some literature the term secular function is still used). In molecular orbital calculations relating to the energy of the electron and its wave function it is also used instead of the characteristic equation. Beyond the home domain. No canonical parent is asserted for Characteristic polynomial of a graph.

Relationships to Other Abstractions¶

Current abstraction Characteristic polynomial of a graph Domain-specific

Parents (2) — more general patterns this builds on

Characteristic polynomial of a graph is a kind of Graph Invariant Domain-specific

Characteristic polynomial of a graph satisfies the defining boundary of Graph Invariant: A graph invariant is a value, polynomial, sequence, multiset, or other mathematical object assigned to a graph such that isomorphic graphs receive the same result, with its definition, graph category, and distinguishing power explicitly stated.
Characteristic polynomial of a graph is a kind of Polynomial Domain-specific

It is the polynomial obtained from the adjacency matrix characteristic polynomial.

Hierarchy paths (2) — routes to 2 parentless roots

Characteristic polynomial of a graph → Graph Invariant

Show alternative path (1)

Neighborhood in Abstraction Space¶

Characteristic polynomial of a graph sits in a moderately populated region (44^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Polynomials & Algebraic Invariants (20 abstractions)

Nearest neighbors

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