The saturated spectral radius for complete graphs

A graph is $K_{r+1}$-saturated if it is $K_{r+1}$-free and adding any missing edge creates a copy of $K_{r+1}$. Kim, Kim, Kostochka, and O conjectured that $K_{r-1}\vee (n-r+1)K_1$ minimizes the spectral radius among all $n$-vertex $K_{r+1}$-saturated graphs. They proved the case $r=2$, and the cases $r=3$ and $r\in \{4,5\}$ were subsequently established by Kim, Kostochka, O, Shi, and Wang, and by Wang and Hou, respectively. We settle the conjecture for all $r\ge 3$: if $n\ge r+1$ and $G$ is an $n$-vertex $K_{r+1}$-saturated graph, then $$\rho (G)\ge \frac{r-2+\sqrt{(r-2{)}^2+4(r-1)(n-r+1)}}{2},$$ with equality if and only if $G\cong K_{r-1}\vee (n-r+1)K_1$. We also prove O’s local two-walk conjecture for every $r\ge 2$: $$\sum _{w\in N_G(v)}{d}_G(w)\ge (r-2)d_G(v)+(r-1)(n-r+1)(v\in V(G))\mathrm{.}$$ If $G$ has no universal vertex, the inequality holds with the additional term $(r-1)(r-2)$ on the right-hand side. This constant is best possible uniformly in $n$ for every fixed $r$, and gives a strict improvement when $r\ge 3$. A corresponding spectral bound follows.