TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 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.

A finite simple graph is bipartite if and only if its adjacency spectrum is symmetric about $0$

Statement

Let $G$ be a finite simple graph with adjacency spectrum ${λ_{1}, \dots, λ_{n}}$ . Then $G$ is bipartite if and only if the multiset ${λ_{1}, \dots, λ_{n}}$ is symmetric about $0$ , that is, if and only if ${λ_{1}, \dots, λ_{n}} = {- λ_{1}, \dots, - λ_{n}}$ as multisets.

Facts & Assumptions

Given: A finite simple graph $G$ with adjacency matrix $A$ and adjacency spectrum ${λ_{1}, \dots, λ_{n}}$ .

[F1]

In a bipartite graph the vertex set splits as $X ⊔ Y$ , and every edge joins a vertex of $X$ to a vertex of $Y$ (A bipartite graph and a proper two-colouring of its vertices).

[L1]

A graph is bipartite exactly when it has no odd cycle (A finite graph is bipartite if and only if it has no odd cycle).

[L2]

The trace $tr (A^{k})$ counts closed walks of length $k$ (The trace of $A (G)^{k}$ counts closed walks of length $k$ ).

[F2]

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

[L3]

Similar matrices have the same trace (Similar matrices have the same trace).

Proof

technique · direct

1.1F1F2

Assume first that $G$ is bipartite with parts $X$ and $Y$ . Let $D$ be the diagonal matrix whose $v v$ entry is $1$ on $X$ and $- 1$ on $Y$ . Then $D^{- 1} = D$ , and [F1] shows that every edge changes sign across the partition, so $D A D = - A$ . Hence $A$ and $- A$ are similar and therefore have the same eigenvalues. By [F2], the spectrum is symmetric about $0$ .

1.2L1L2F2L3algebra

Conversely, assume the spectrum is symmetric about $0$ . Because [F2] cites the real spectral theorem for the real symmetric matrix $A$ , there is an invertible matrix $P$ with $P^{- 1} A P = diag (λ_{1}, \dots, λ_{n})$ . For every odd integer $r \geq 1$ , this gives $P^{- 1} A^{r} P = diag (λ_{1}^{r}, \dots, λ_{n}^{r})$ , so [L3] yields $tr (A^{r}) = \sum_{i = 1}^{n} λ_{i}^{r} = 0$ after the odd powers cancel in symmetric pairs. By [L2], $G$ has no closed walk of odd length. An odd cycle would itself be an odd closed walk, so $G$ has no odd cycle. Therefore [L1] makes $G$ bipartite.

2.1step 1.1step 1.2∎

Steps 1.1 and 1.2 prove the two directions of the equivalence.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

21 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

Steve Butler, Spectral Graph Theory course notes, lectures 3-4 (standard reference, not scraped)

A finite simple graph is bipartite if and only if its adjacency spectrum is symmetric about 00