TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-28

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The complete graph $K_{n}$ has adjacency spectrum ${n - 1, (- 1)^{n - 1}}$

Statement

For every integer $n \geq 1$ , the complete graph $K_{n}$ has adjacency spectrum

${n - 1, (- 1)^{n - 1}},$

that is, the eigenvalue $n - 1$ once and the eigenvalue $- 1$ with multiplicity $n - 1$ .

Facts & Assumptions

Given: An integer $n \geq 1$ and the complete graph $K_{n}$ .

[F1]

In $K_{n}$ , every pair of distinct vertices is adjacent (Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

[F2]

The adjacency spectrum is the multiset of eigenvalues of the adjacency matrix (Adjacency spectrum, spectral radius, and cospectral graphs).

Proof

technique · direct

1.1F1algebra

In the standard vertex order, the adjacency matrix of $K_{n}$ is $J - I$ , where $J$ is the all-ones matrix, because [F1] makes every off-diagonal entry equal to $1$ and every diagonal entry equal to $0$ . The all-ones vector $1$ satisfies $J 1 = n 1$ , so $(J - I) 1 = (n - 1) 1$ .

2.1step 1.1algebra

If $x$ is orthogonal to $1$ , then the coordinates of $x$ sum to $0$ , so $J x = 0$ . Hence $(J - I) x = - x$ . The subspace $1^{⊥}$ has dimension $n - 1$ , so $- 1$ is an eigenvalue with multiplicity at least $n - 1$ ; together with step 1.1 this accounts for all $n$ dimensions.

3.1step 1.1step 2.1F2∎

Therefore the eigenvalues of the adjacency matrix are exactly $n - 1$ and $- 1$ with the stated multiplicities, which is the spectrum by [F2].

Depends on

Used by

Cayley's formula follows again from the matrix-tree theorem Corollary
Kirchhoff's formula gives τ(K₄)=16 Example

Dependency tree · two levels

11 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Richard P. Stanley, MIT 18.314 handout, Example 1.11 (standard reference, not scraped)

The complete graph KnKn​ has adjacency spectrum {n−1,(−1)n−1}{n−1,(−1)n−1}