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.

A high-degree vertex forces a large centered adjacency norm

Statement

Let $A$ be the adjacency matrix of a simple graph on $n \geq 1$ vertices, $J$ the all-ones matrix, and $D$ the largest vertex degree. With Euclidean operator norms, $∥ A - J / n ∥ \geq \sqrt{D} - 1.$ For the article's centering $Δ_{A} = A - p J$ this applies when $p = 1 / n$ .

Facts & Assumptions

[F1]

The Euclidean operator norm is $∥ B ∥ = \sup_{∥ x ∥_{2} = 1} ∥ B x ∥_{2}$ (The operator norm is zero on the zero domain and otherwise is max_‖ v‖=1‖ Tv‖).

[F2]

Cauchy–Schwarz bounds a Euclidean inner product by the product of the two norms, and the Euclidean norm satisfies the triangle inequality (Cauchy-Schwarz |⟨ x,y⟩| ≤ ‖ x‖₂‖ y‖₂ with its equality case, the triangle inequality for ‖·‖₂, the parallelogram law and polarisation).

[F3]

The adjacency matrix is symmetric, its entries are edge indicators, and the degree of a vertex is its row sum (Adjacency, degrees, graph Laplacian, and spectral notation). The centering for $G (n, p)$ is $Δ_{A} = A - p J$ (Centered graph matrices and reference degree).

Proof

Given: The hypotheses and objects in the Statement.

Goal: Establish the asserted conclusions.

1.1F1F2F3given

At a vertex $u$ of degree $D$ , the column $A e_{u}$ has exactly $D$ entries equal to one and all other entries zero. Since $e_{u}$ is a unit vector, [F1] gives $∥ A ∥ \geq ∥ A e_{u} ∥_{2} = \sqrt{D}$ . For every unit vector $x$ , [F2] gives $∣ \sum_{i} x_{i} ∣ \leq \sqrt{n}$ , so $∥ J x ∥_{2} = \sqrt{n} ∣ \sum_{i} x_{i} ∣ \leq n$ . Equality holds at the unit constant vector. Thus $∥ J / n ∥ = 1$ .

2.1F1F2F3step 1.1algebra∎

The Euclidean triangle inequality applied to $(A - J / n) x + (J / n) x$ and then the supremum formula give $∥ A ∥ \leq ∥ A - J / n ∥ + ∥ J / n ∥$ . Insert step 1.1 and rearrange. At $p = 1 / n$ , [F3] identifies $A - J / n$ with $Δ_{A}$ .

Depends on

Used by · 2

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.