PropositionStatement: 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.

Ordered edge counts and centered cut vectors

Statement

Let $(V, A)$ be a network: $V$ is a nonempty finite set, $n = ∣ V ∣$ , and $A$ is a real symmetric nonnegative matrix indexed by $V$ . Put $d (x) = \sum_{y \in V} A_{x y}$ , $D = diag (d (x))$ , $L = D - A$ , and let $J$ be the matrix all of whose entries are $1$ . For $X \subseteq V$ , let $X^{c} = V ∖ X$ and let $1_{X}$ be its indicator, equal to $1$ on $X$ and $0$ elsewhere. For subsets $X, Y \subseteq V$ , define the ordered weight count $e (X, Y) = \sum_{x \in X} \sum_{y \in Y} A_{x y}$ ; then $e (X, Y) = 1_{X}^{T} A 1_{Y}$ .

For $f = ∣ X^{c} ∣ 1_{X} - ∣ X ∣ 1_{X^{c}}$ , one has $f^{T} f = n ∣ X ∣ ∣ X^{c} ∣$ , $J f = 0$ , and $f^{T} L f = n^{2} e (X, X^{c})$ . If $X \subseteq Y$ , then $2 e (X, Y^{c}) = e (X, X^{c}) + e (Y, Y^{c}) - e (Y ∖ X, (Y ∖ X)^{c})$ . These are ordered-pair weight counts; no diagonal entry contributes to a cut count.

Statement references

Finite symmetric networks and loop removal

Finite vertex Hilbert space in the article convention

The difference a ∖ b, the symmetric difference a △ b, and the complement X ∖ a relative to a set X

A finite sum in a commutative monoid indexed by an arbitrary finite set

Facts & Assumptions

[F1]

The network definition supplies symmetric $A$ , its row-sum degree matrix $D$ , and $L = D - A$ ; diagonal entries are allowed. See Finite symmetric networks and loop removal.

[F2]

Matrix action and the vertex pairing are finite coordinate sums. See Finite vertex Hilbert space in the article convention and A finite sum in a commutative monoid indexed by an arbitrary finite set.

[F3]

Relative complements and set differences consist of the elements in the first set that are not in the second. See The difference a ∖ b, the symmetric difference a △ b, and the complement X ∖ a relative to a set X.

Proof

Given: A network $(V, A)$ and subsets $X, Y \subseteq V$ as in the statement.

Goal: Establish the displayed indicator, cut-vector and nested-cut identities.

1.1F1F2F3

By the coordinate definitions, $1_{X}^{T} A 1_{Y} = \sum_{x \in V} \sum_{y \in V} 1_{X} (x) A_{x y} 1_{Y} (y) = e (X, Y)$ . Interchanging the finite indices and using symmetry gives $e (P, Q) = e (Q, P)$ for any subsets $P, Q$ . The defining sum is additive over disjoint unions in either argument. Since $X$ and $X^{c}$ are disjoint, a pair contributing to $e (X, X^{c})$ never has equal coordinates, so no diagonal entry contributes.

1.2F2F3algebra

Put $a = ∣ X ∣$ and $b = ∣ X^{c} ∣$ . The sets $X$ and $X^{c}$ partition $V$ , so $a + b = n$ ; the vector $f$ equals $b$ on $X$ and $- a$ on $X^{c}$ . Hence $f^{T} f = a b^{2} + b a^{2} = n a b$ and $\sum_{x} f (x) = a b - b a = 0$ . Each coordinate of $J f$ is this sum, giving $J f = 0$ .

2.1F1F2step 1.1step 1.2algebra

Expanding the row sums in $D$ and using symmetry yields $f^{T} L f = \frac{1}{2} \sum_{x, y \in V} A_{x y} (f (x) - f (y))^{2}$ . The difference is zero within either part and has square $(a + b)^{2} = n^{2}$ across the partition. The two oriented crossing sums are equal, so $f^{T} L f = n^{2} e (X, X^{c})$ . This calculation also covers empty $X$ or $X^{c}$ and arbitrary diagonal weights.

3.1F3step 1.1algebra∎

Suppose $X \subseteq Y$ and put $B = Y ∖ X$ and $C = Y^{c}$ . The sets $X, B, C$ partition $V$ . Additivity and symmetry give $e (X, X^{c}) = e (X, B) + e (X, C)$ , $e (Y, Y^{c}) = e (X, C) + e (B, C)$ , and $e (B, B^{c}) = e (X, B) + e (B, C)$ . Substitution gives $e (X, X^{c}) + e (Y, Y^{c}) - e (B, B^{c}) = 2 e (X, C) = 2 e (X, Y^{c})$ , as required.

Depends on

Used by · 4

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.