LemmaStatement: AI-generatedProof: AI-generated

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.

Disconnected and bipartite spectral witnesses

Statement

For a labelled simple $d$ -regular graph $G$ on $n \geq 2$ vertices with $d > 0$ , let $A$ be its adjacency matrix and write $ρ_{0} (A) = ∥ A - (d / n) J ∥_{o p}$ , where $J$ is the all-ones matrix. A connected component is a maximal set of vertices joined by paths; a component is bipartite if it splits into two disjoint parts with each edge joining different parts. If $G$ is disconnected, or has a bipartite connected component, then $ρ_{0} (A) = d$ . Consequently, for any $0 < t < d$ , the inequality $ρ_{0} (A) < t$ excludes both obstructions.

Statement references

Ordered eigenvalues and the centered regular norm

Pairings, simple-graph conditioning and model transfer

The adjacency matrix of a finite simple graph

Walks, paths, connectedness and components in a simple graph on an arbitrary vertex set

Facts & Assumptions

[F1]

Ordered eigenvalues and the centered regular norm identifies $ρ_{0} (A)$ with the norm of $A$ on $1^{⊥}$ . Its proof step 1.1 bounds every adjacency eigenvalue in absolute value by $d$ , using a maximum-modulus coordinate of a nonzero eigenvector and the nonnegative row sum $d$ .

[F2]

Pairings, simple-graph conditioning and model transfer supplies the labelled simple regular graph and incidence conventions.

[F3]

The adjacency matrix of a finite simple graph defines $A_{v w}$ to be $1$ for an edge and $0$ otherwise; hence $(A x)_{v}$ is the sum of $x_{w}$ over neighbours $w$ of $v$ .

[F4]

Walks, paths, connectedness and components in a simple graph on an arbitrary vertex set defines paths, connectedness and connected components.

Proof

Given: The regular graph and either of the stated obstructions.

Goal: Exhibit a mean-zero eigenvector of eigenvalue $d$ or $- d$ .

1.1F1F2F3F4givenalgebra

If $C$ is a nonempty proper connected component, its indicator $1_{C}$ satisfies $A 1_{C} = d 1_{C}$ : vertices in $C$ have all $d$ neighbours in $C$ , and vertices outside have none in $C$ . Thus $x = 1_{C} - (∣ C ∣ / n) 1$ is nonzero, has coordinate sum zero and satisfies $A x = d x$ . By [F1] this forces $ρ_{0} (A) \geq d$ , while the eigenvalue bound gives the reverse inequality.

2.1F1F2F3F4givenalgebra∎

If a connected component has bipartition $L, R$ , counting its edges at each end gives $d ∣ L ∣ = d ∣ R ∣$ . Since $d > 0$ , $∣ L ∣ = ∣ R ∣$ . Let $y$ equal $1$ on $L$ , $- 1$ on $R$ and zero elsewhere. It is nonzero, has coordinate sum zero and satisfies $A y = - d y$ , because every neighbour of a vertex in the component has the opposite sign. Again [F1] forces $ρ_{0} (A) = d$ . Either obstruction therefore contradicts $ρ_{0} (A) < t < d$ , proving the conclusion.

Depends on

Used by · 1

Friedman spectral expansion in the uniform simple model

Dependency tree · 2 levels

Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.