Variance bound for the degree deviation of connected graphs

Counterexample: the degree-variance spectral bound fails even for bounded-degree trees

Conjecture 1.5 of Felix Goldberg, New results on eigenvalues and degree deviation, arXiv:1403.2629, asserts that every connected simple graph $G$ satisfies

$$\rho(G)-\overline d(G)\leq\sqrt{\operatorname{var}(G)}, \qquad \overline d(G)=\frac1n\sum_{v\in V(G)}d(v), \qquad \operatorname{var}(G)=\frac1n\sum_{v\in V(G)} \bigl(d(v)-\overline d(G)\bigr)^2, \tag{1}$$

where $n=|V(G)|$ and $\rho(G)$ is the spectral radius of its adjacency matrix. We disprove (1) by an explicit 12-vertex graph, an infinite family of lollipop graphs, and an infinite family of connected bipartite trees of maximum degree three. In fact, no universal constant multiplying the right-hand side can repair the inequality.

A 12-vertex connected counterexample

For $n\geq5$, let $L_n$ consist of a complete graph on four vertices together with a path on $n-4$ additional vertices, attached by a single edge to one clique vertex. Its degrees are

$$4,\ 3,\ 3,\ 3,\ \underbrace{2,\ldots,2}_{n-5\text{ times}},\ 1. \tag{2}$$

Consequently,

$$\sum_v d(v)=2n+4, \qquad \sum_v d(v)^2=4n+24, \tag{3}$$

and hence

$$\overline d(L_n)=2+\frac4n, \qquad \operatorname{var}(L_n) =\frac{4n+24}{n}-\left(2+\frac4n\right)^2 =\frac{8(n-2)}{n^2}. \tag{4}$$

Write $A_n$ for the adjacency matrix of $L_n$, and choose a vector $x$ that equals $1$ on the four clique vertices, equals $1/3$ on the first path vertex, and vanishes elsewhere. The Rayleigh principle gives

$$\rho(L_n)\geq\frac{x^{\mathsf T}A_nx}{x^{\mathsf T}x} =\frac{12+2/3}{4+1/9} =\frac{114}{37}. \tag{5}$$

At $n=12$, formulas (4) and (5) yield

$$\overline d(L_{12})=\frac73, \qquad \operatorname{var}(L_{12})=\frac59, \qquad \rho(L_{12})-\overline d(L_{12}) \geq\frac{83}{111} >\frac{\sqrt5}{3}. \tag{6}$$

The final inequality is exact: $83^2=6889>6845=5\cdot37^2$. Thus $L_{12}$ is a concrete connected counterexample to (1).

In fact the entire family violates (1) for every $n\geq12$. Indeed,

$$\left(\frac{114}{37}-2-\frac4n\right)^2 -\frac{8(n-2)}{n^2} =\frac{1600n^2-22792n+43808}{1369n^2}. \tag{7}$$

The numerator equals $704>0$ at $n=12$, and its successive difference is $3200n-21192>0$ for every $n\geq12$. Since the quantity being squared on the left is positive, (7) proves the strict violation for all such $n$.

For an even simpler instance requiring only the clique bound $\rho(L_n)\geq\rho(K_4)=3$, take $n=14$. Then

$$\rho(L_{14})\geq3 >\frac{16+2\sqrt6}{7} =\overline d(L_{14})+ \sqrt{\operatorname{var}(L_{14})}, \tag{8}$$

because $2\sqrt6<5$.

Counterexamples among subcubic bipartite trees

Begin with a three-vertex path $a-b-c$. Attach two leaves to $a$, one leaf to $b$, and two leaves to $c$, obtaining an eight-vertex tree with three vertices of degree three and five leaves. For $n\geq9$, extend any one of these leaves by a path consisting of $n-8$ new vertices. Denote the resulting tree by $T_n$. Its degree multiset is

$$3,\ 3,\ 3,\ \underbrace{2,\ldots,2}_{n-8\text{ times}},\ 1,\ 1,\ 1,\ 1,\ 1. \tag{9}$$

In particular, $T_n$ is connected, bipartite, and has maximum degree three. Since $T_n$ has $n-1$ edges,

$$\sum_v d(v)^2=27+4(n-8)+5=4n, \qquad \overline d(T_n)=2-\frac2n, \tag{10}$$

so that

$$\operatorname{var}(T_n) =4-\left(2-\frac2n\right)^2 =\frac8n-\frac4{n^2}. \tag{11}$$

Choose a vector $y$ that equals $2$ on $a,b,c$, equals $1$ on the five original leaves, and vanishes on every newly added path vertex. The two central edges contribute $16$ to $y^{\mathsf T}A(T_n)y$, and the five center-leaf edges contribute $20$. Therefore

$$\rho(T_n)\geq \frac{y^{\mathsf T}A(T_n)y}{y^{\mathsf T}y} =\frac{36}{17}. \tag{12}$$

Combining (10)--(12),

$$\left(\frac{36}{17}-2+\frac2n\right)^2 -\operatorname{var}(T_n) =\frac{4n^2-2176n+2312}{289n^2}. \tag{13}$$

The numerator in (13) equals $140>0$ at $n=543$, and its successive difference is $8n-2172>0$ for every $n\geq543$. Hence every $T_n$ with $n\geq543$ violates the conjecture.

Moreover, (11) and (12) show that

$$\frac{\rho(T_n)-\overline d(T_n)} {\sqrt{\operatorname{var}(T_n)}} \geq \frac{2n+34}{17\sqrt{8n-4}} \longrightarrow\infty. \tag{14}$$

Thus even restricting to connected bipartite trees of maximum degree three, there exists no absolute constant $C$ for which

$$\rho(G)-\overline d(G) \leq C\sqrt{\operatorname{var}(G)} \tag{15}$$

holds universally. Goldberg's positive result for graphs with clique number at least $n/2$ is unaffected: both counterexample families lie outside that additional hypothesis.