LemmaStatement: AI-adaptedProof: 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.

Nested-cut polarization identity

PDF p. 20: Proof of Lemma 3.7, opening identity; PDF p. 21: Proof of Lemma 3.7, opening identity

Statement

Let $G = (V, E)$ be a finite undirected graph with nonempty vertex set, at most one edge between each pair of vertices, and possible loops. Its adjacency entry $A_{x, y}$ is $1$ when ${x, y} \in E$ and $0$ otherwise. For $P, Q \subseteq V$ , write $e (P, Q) = \sum_{p \in P} \sum_{q \in Q} A_{p, q}$ and $P^{c} = V ∖ P$ . If $X \subseteq Y \subseteq V$ , then

$e (X, Y^{c}) = \frac{e (X, X^{c}) + e (Y, Y^{c}) - e (Y ∖ X, (Y ∖ X)^{c})}{2} .$

Facts & Assumptions

[F1]

The graph adjacency matrix is symmetric and nonnegative, and the displayed $e (P, Q)$ is its ordered-pair count; complements are relative to $V$ (Oriented edge count between sets).

[F2]

For a nonempty finite set with a symmetric nonnegative matrix and the same ordered weight count, nested sets satisfy $2 e (X, Y^{c}) = e (X, X^{c}) + e (Y, Y^{c}) - e (Y ∖ X, (Y ∖ X)^{c})$ (Ordered edge counts and centered cut vectors).

Proof

Given: $G$ , $X$ and $Y$ as in the statement.

Goal: Prove the displayed nested-cut identity.

1.1givenF1F2

By [F1], $A$ is a symmetric nonnegative matrix indexed by the nonempty finite set $V$ . Its ordered weight count and relative complements are exactly those in the statement, so the hypotheses and notation of [F2] apply to $X \subseteq Y$ .

2.1F2step 1.1algebra∎

Applying [F2] gives twice the left-hand side equal to the numerator on the right. Dividing by $2$ proves the identity, including when one of the sets is empty.

Source notes

The identity is attributed to the opening of the proof of Lemma 3.7 in the cited article. The proof above instead applies the independently supplied cut-calculus proposition.

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.

Sources

Expander graphs are globally synchronizing · PDF pp. 20–21, proof of Lemma 3.7, opening identity