C1 · Tightness
Universal
Δg = δΔv + (λ-aᵢⱼ)δ² ≥ 0
Pairwise rounding strictly decreases the fractional-coordinate count and terminates at a no-worse integral point.
Densest-k-Subgraph: universal proof audit
VQt4w3lElX · tight relaxation · strict landscape · finite exact convergence
C2 · Dichotomy
Universal
dᵀ(A+λI)d = 2(λ-aᵢⱼ) > 0
KKT gives integral local maxima or an explicit zero-gradient, positive-curvature saddle direction.
C3 · Algorithm 1
35 updates
4,039 nodes · 88,234 edges · gap 0
The equation-level proof closes, and the original SNAP Facebook protocol takes the predicted final γ=1 jump to exact integrality.
Negative control
The constant-2kL denominator remains fractional at all 4,039 coordinates after 50,000 updates with gap 0.131515. The legacy eigenvector/snap optimizer remains disclosed as non-Algorithm-1 corroboration.