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.

✓ 8 results · all verified · 3 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 5 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Algebraic and Spectral Graph Theory — Examples

1 · Prerequisites

2 · Summary

These examples check the page's standard spectral computations on small named graphs and record two false converses that the main theorems do not justify: cospectrality does not force isomorphism, and positive algebraic connectivity detects connectedness rather than $2$ -connectedness.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-28Open item page →

The cycle $C_{4}$ has adjacency spectrum ${2, 0, 0, - 2}$

Example

The cycle graph $C_{4}$ has adjacency spectrum ${2, 0, 0, - 2}$ .

Facts & Assumptions

Given: The cycle graph $C_{4}$ .

[L1]

The cycle graph $C_{n}$ has adjacency eigenvalues $2 \cos (2 π j / n)$ for $0 \leq j < n$ (The cycle graph $C_{n}$ has adjacency spectrum ${2 \cos (2 π j / n) : 0 \leq j < n}$ ).

Verification

technique · direct

1.1L1algebra

Applying [L1] with $n = 4$ gives the eigenvalues $2 \cos (0) = 2$ , $2 \cos (π / 2) = 0$ , $2 \cos (π) = - 2$ , and $2 \cos (3 π / 2) = 0$ .

2.1step 1.1∎

Reordering these values from largest to smallest yields ${2, 0, 0, - 2}$ .

ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passaudited 2026-08-28Open item page →

A disconnected graph has a Laplacian kernel spanned by its component indicators

Example

Let $G$ have vertex set ${1, 2, 3, 4}$ and edge set ${{1, 2}, {3, 4}}$ . Then

$\ker L (G) = span {(1, 1, 0, 0)^{T}, (0, 0, 1, 1)^{T}} .$

Facts & Assumptions

Given: The graph $G$ with components ${1, 2}$ and ${3, 4}$ .

[L1]

The Laplacian kernel is spanned by the indicator vectors of the connected components (The multiplicity of the Laplacian eigenvalue $0$ equals the number of connected components).

Verification

technique · direct

1.1given

The graph $G$ has exactly two connected components, namely ${1, 2}$ and ${3, 4}$ . Their indicator vectors are $(1, 1, 0, 0)^{T}$ and $(0, 0, 1, 1)^{T}$ .

2.1step 1.1L1∎

By [L1], those two indicator vectors span the Laplacian kernel. They are linearly independent, so this displayed span is exactly $\ker L (G)$ .

ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passaudited 2026-08-28Open item page →

Kirchhoff's formula gives $τ (K_{4}) = 16$

Example

The complete graph $K_{4}$ has exactly $16$ spanning trees.

Facts & Assumptions

Given: The complete graph $K_{4}$ .

[L1]

For a regular graph, $τ (G) = \frac{1}{∣ V (G) ∣} \prod_{j = 2}^{∣ V (G) ∣} (d - λ_{j})$ (The matrix-tree theorem becomes an eigenvalue product formula).

[L2]

The adjacency eigenvalues of $K_{4}$ are $3, - 1, - 1, - 1$ (The complete graph $K_{n}$ has adjacency spectrum ${n - 1, (- 1)^{n - 1}}$ ).

Verification

technique · direct

1.1L1L2algebra

The graph $K_{4}$ is $3$ -regular and has four vertices, so [L1] and [L2] give $τ (K_{4}) = \frac{1}{4} (3 - (- 1))^{3} = \frac{1}{4} \cdot 4^{3} = 16$ .

2.1step 1.1∎

Therefore Kirchhoff's product formula recovers the count $τ (K_{4}) = 16$ .

ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-28Open item page →

The graph $K_{3, 3}$ has adjacency spectrum ${3, 0, 0, 0, 0, - 3}$

Example

The complete bipartite graph $K_{3, 3}$ has adjacency spectrum ${3, 0, 0, 0, 0, - 3}$ .

Facts & Assumptions

Given: The graph $K_{3, 3}$ .

[L1]

The graph $K_{m, n}$ has adjacency spectrum ${\sqrt{m n}, 0^{m + n - 2}, - \sqrt{m n}}$ (The complete bipartite graph $K_{m, n}$ has adjacency spectrum ${\sqrt{m n}, 0^{m + n - 2}, - \sqrt{m n}}$ ).

Verification

technique · direct

1.1L1algebra

Applying [L1] with $m = n = 3$ gives the eigenvalues $\sqrt{9} = 3$ , $0^{3 + 3 - 2} = 0^{4}$ , and $- \sqrt{9} = - 3$ .

2.1step 1.1∎

So the ordered spectrum is ${3, 0, 0, 0, 0, - 3}$ .

ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-28Open item page →

The two-subset model reproduces the Petersen spectrum

Example

The Petersen graph, realised on the two-element subsets of a five-element set, has adjacency spectrum ${3, 1^{5}, (- 2)^{4}}$ .

Facts & Assumptions

Given: The Petersen graph on $[Ω]^{2}$ for a five-element set $Ω$ .

[F1]

This graph is the Petersen graph exactly when adjacency means disjointness of the two-element subsets (The Petersen graph on the two-element subsets of a five-element set, adjacent when disjoint).

[L1]

The Petersen graph has adjacency spectrum ${3, 1^{5}, (- 2)^{4}}$ (The Petersen graph has adjacency spectrum ${3, 1^{5}, (- 2)^{4}}$ ).

Verification

technique · direct

1.1F1

By [F1], the displayed two-subset construction is precisely the Petersen graph, not merely an isomorphic copy under a different naming convention.

2.1step 1.1L1∎

Therefore [L1] applies directly and yields the spectrum ${3, 1^{5}, (- 2)^{4}}$ .

CounterexampleConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-08-28Open item page →

Two cospectral graphs need not be isomorphic

Statement refuted

If two finite simple graphs are cospectral, then they are isomorphic.

Facts & Assumptions

Given: The star $K_{1, 4}$ and the disjoint union $C_{4} ⊔ K_{1}$ .

[L1]

The graph $K_{1, 4}$ has spectrum ${2, 0, 0, 0, - 2}$ (The complete bipartite graph $K_{m, n}$ has adjacency spectrum ${\sqrt{m n}, 0^{m + n - 2}, - \sqrt{m n}}$ ).

[L2]

The graph $C_{4}$ has spectrum ${2, 0, 0, - 2}$ (The cycle graph $C_{n}$ has adjacency spectrum ${2 \cos (2 π j / n) : 0 \leq j < n}$ ).

[L3]

Isomorphic graphs have the same spectrum (The adjacency spectrum is an isomorphism invariant).

[F1]

Cospectral graphs are those with the same adjacency spectrum (Adjacency spectrum, spectral radius, and cospectral graphs).

Counterexample

technique · direct

1.1L1L2F1

By [L1], the star $K_{1, 4}$ has spectrum ${2, 0, 0, 0, - 2}$ . By [L2], the cycle $C_{4}$ has spectrum ${2, 0, 0, - 2}$ , so adjoining an isolated vertex contributes one more zero eigenvalue and gives the same spectrum for $C_{4} ⊔ K_{1}$ . Hence the two graphs are cospectral by [F1].

2.1step 1.1L3

The graphs are not isomorphic, because $K_{1, 4}$ is connected while $C_{4} ⊔ K_{1}$ is not. Therefore the converse of [L3] fails.

3.1step 1.1step 2.1∎

So cospectral graphs need not be isomorphic.

False statementConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-08-28Open item page →

FALSE: positive second Laplacian eigenvalue characterises 2-connectivity

Statement

False claim. A finite simple graph has positive second Laplacian eigenvalue if and only if it is $2$ -connected.

Facts & Assumptions

Given: The path graph $P_{3}$ on vertices $1 - 2 - 3$ .

[L1]

A graph with positive algebraic connectivity is connected, and conversely (A finite simple graph is connected if and only if its algebraic connectivity is positive).

[F1]

The algebraic connectivity is the second-smallest Laplacian eigenvalue (The algebraic connectivity of a finite simple graph).

[F2]

A graph is $2$ -connected when deleting any one vertex leaves it connected (Vertex cuts, edge cuts, vertex connectivity $κ (G)$ and edge connectivity $λ (G)$ , with conventions for complete and one-vertex graphs).

Refutation

technique · direct

1.1L1F1

The path $P_{3}$ is connected, so [L1] and [F1] show that its second Laplacian eigenvalue is positive.

1.2F2

Deleting the middle vertex of $P_{3}$ leaves two isolated vertices, which is disconnected. Therefore [F2] shows that $P_{3}$ is not $2$ -connected.

2.1step 1.1step 1.2∎

So $P_{3}$ has positive second Laplacian eigenvalue but is not $2$ -connected, refuting the claim.

False statementConstruction: AI-adaptedVerification: AI-adaptedprecheck passaudited 2026-08-28Open item page →

FALSE: the matrix-tree theorem works only for one distinguished cofactor

Statement

False claim. The matrix-tree theorem computes the spanning-tree count from only one special cofactor of the Laplacian; deleting a different row and column can change the answer.

Facts & Assumptions

Given: A finite simple graph $G$ .

[L1]

Every principal cofactor of the Laplacian equals $τ (G)$ (Kirchhoff's matrix-tree theorem).

Refutation

technique · direct

1.1L1

By [L1], for every vertex index $i$ the principal cofactor obtained by deleting row $i$ and column $i$ has determinant $τ (G)$ . So the value does not depend on a distinguished choice of index.

2.1step 1.1∎

This is exactly the negation of the false claim, so the claim is refuted.

Algebraic and Spectral Graph Theory — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

The cycle C4C4​ has adjacency spectrum {2,0,0,−2}{2,0,0,−2}

Example

Facts & Assumptions

Verification

A disconnected graph has a Laplacian kernel spanned by its component indicators

Example

Facts & Assumptions

Verification

Kirchhoff's formula gives τ(K4)=16τ(K4​)=16

Example

Facts & Assumptions

Verification

The graph K3,3K3,3​ has adjacency spectrum {3,0,0,0,0,−3}{3,0,0,0,0,−3}

Example

Facts & Assumptions

Verification

The two-subset model reproduces the Petersen spectrum

Example

Facts & Assumptions

Verification

Two cospectral graphs need not be isomorphic

Statement refuted

Facts & Assumptions

Counterexample

FALSE: positive second Laplacian eigenvalue characterises 2-connectivity

Statement

Facts & Assumptions

Refutation

FALSE: the matrix-tree theorem works only for one distinguished cofactor

Statement

Facts & Assumptions

Refutation

Sources

The cycle $C_{4}$ has adjacency spectrum ${2, 0, 0, - 2}$

Kirchhoff's formula gives $τ (K_{4}) = 16$

The graph $K_{3, 3}$ has adjacency spectrum ${3, 0, 0, 0, 0, - 3}$