ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

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 disconnected graph on concentric circles separates the rings

Example

Let $V = {1, \dots, 8}$ and, for $j \in {0, 1, 2, 3}$ , set $x_{j + 1} = (\cos (π j / 2), \sin (π j / 2))$ and $x_{j + 5} = 3 (\cos (π j / 2), \sin (π j / 2))$ . Build a graph with unit-weight edges ${1, 2}, {2, 3}, {3, 4}, {4, 1}$ and ${5, 6}, {6, 7}, {7, 8}, {8, 5}$ , and no other edges. Deterministic unnormalized spectral clustering with $k = 2$ and no row normalization returns the two concentric rings as its clusters. This finite graph example makes no statement about manifold recovery for other graph constructions.

Example references

Ulrike von Luxburg, A Tutorial on Spectral Clustering, Statistics and Computing 17(4), 2007

Jean Gallier, Notes on Elementary Spectral Graph Theory: Applications to Graph Clustering Using Normalized Cuts, 2013

Graph diagram

Nodes $1$ – $4$ lie on the inner radius-one circle and nodes $5$ – $8$ on the outer radius-three circle. Each polygon edge has unit weight; there are no edges between the circles. The drawing uses the exact vertex order and support specified in the Example.

diagram failed to render:
\begin{tikzpicture}
\node[draw,circle] (v1) at (0,1) {$1$};
\node[draw,circle] (v2) at (1,0) {$2$};
\node[draw,circle] (v3) at (0,-1) {$3$};
\node[draw,circle] (v4) at (-1,0) {$4$};
\node[draw,circle] (v5) at (0,3) {$5$};
\node[draw,circle] (v6) at (3,0) {$6$};
\node[draw,circle] (v7) at (0,-3) {$7$};
\node[draw,circle] (v8) at (-3,0) {$8$};
\draw (v1)--(v2)--(v3)--(v4)--cycle;
\draw (v5)--(v6)--(v7)--(v8)--cycle;
\end{tikzpicture}

Facts & Assumptions

Given: The eight vertices are ordered by radius as in the Example, and the graph consists of the two unit-weight four-cycles with no cross-edges.

[F1]

Finite weighted graph Laplacian: the support graph has edge ${i, j}$ exactly when $w_{i j} > 0$ .

[F2]

Quadratic form and kernel of a weighted graph Laplacian: $L$ is positive semidefinite and its kernel consists of vectors constant on each support component.

[F3]

Deterministic weighted spectral clustering with explicit isolate and eigenspace conventions: unnormalized mode chooses the first $k$ eigenvectors increasingly; the zero-mode basis starts at $n^{- 1 / 2} 1$ and then uses projected coordinate vectors in vertex order, and Lloyd centers use the smallest-index row followed by farthest-first selection.

Verification

1.1givenF1F2algebra

The support components are $C_{1} = {1, 2, 3, 4}$ and $C_{2} = {5, 6, 7, 8}$ . By [F2], $L ⪰ 0$ and $E_{0} = \ker L = span (1_{C_{1}}, 1_{C_{2}})$ has dimension $2$ , so the two smallest eigenvalues are both $0$ .

2.1givenF2F3step 1.1constructalgebra

The prescribed first vector is $q_{0} = 1 / \sqrt{8}$ . The projection of $e_{1}$ onto $E_{0}$ is $\frac{1}{4} 1_{C_{1}}$ . Its inner product with $q_{0}$ is $1 / \sqrt{8}$ , so subtracting that projection gives $\frac{1}{8} (1_{C_{1}} - 1_{C_{2}})$ , with norm $1 / \sqrt{8}$ . Thus the next vector is $q_{1} = (1_{C_{1}} - 1_{C_{2}}) / \sqrt{8}$ . The embedding rows are $(1 / \sqrt{8}, 1 / \sqrt{8})$ on $C_{1}$ and $(1 / \sqrt{8}, - 1 / \sqrt{8})$ on $C_{2}$ .

3.1F3step 2.1algebra∎

The first center is the row for vertex $1$ . Every outer-ring row is farther from it than any other inner-ring row, so farthest-first chooses vertex $5$ by the smallest-index tie rule. Each ring's rows equal its center, while the two ring row values are distinct; nearest-center assignments are therefore exactly $C_{1}, C_{2}$ . Their means equal the selected centers, so the first Lloyd update is fixed and the algorithm returns the two rings.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

8 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

Ulrike von Luxburg, A Tutorial on Spectral Clustering, Statistics and Computing 17(4), 2007 (standard reference, not scraped)
Jean Gallier, Notes on Elementary Spectral Graph Theory: Applications to Graph Clustering Using Normalized Cuts, 2013 (standard reference, not scraped)