Quadratic form built from a graph

Question

Consider a finite graph $\Gamma$ with $n$ vertices. We can associate a quadratic form on $\mathbb{R}^n$ to $\Gamma$ by the following rule:

$$q_{\Gamma} : = \sum \limits_{k=1}^n x_k^2 - \sum \limits_{\text{all the edges i-j}} x_ix_j. $$

I am trying to prove that if we want $q_{\Gamma} > 0$ we need to require that $\Gamma$ has at most one vertex of the degree 3.

It seems to me that it is not even true. We need at least suppose that the graph is connected. But still I am not able to prove it. P.S. I successfully proved that $\Gamma$ cannot contain any cicles.

Answer 1

Let $A$ be the adjacency matrix of a graph $\Gamma.$ Let $B=I-\frac{1}{2}A.$ The quadratic form $q_{\Gamma}$ can be expressed $q_{\Gamma}(x)=x^{T}Bx$, where $x=(x_{1},x_{2},\dots,x_{n}).$ We have the following standard result:

$$q_{\Gamma} > 0 \iff B \text{ is positive definite }\iff \text{ all eigenvalues of }B \text{ are } > 0.$$

The eigenvalues of $B$ are precisely $\{1-\frac{\lambda}{2}:\lambda \text{ an e-value of } A\}.$ Another standard result: the largest eigenvalue of $A$ is at most $\Delta_{\Gamma}$, the maximum degree of $\Gamma.$ So the smallest eigenvalue of $B$ is bounded below by $1-\frac{\Delta_{\Gamma}}{2}.$ From this, you get, that $2>\Delta_{\Gamma}$ implies $q_{\Gamma}>0.$

To go the other way, you might use some lower bound on the largest eigenvalue of $A$, which is usually denoted $\lambda_{1}.$ One well-known lower bound is $\lambda_{1} \geq \frac{2|E(\Gamma)|}{n}$, which is the average degree of $\Gamma.$ $1-\frac{\lambda_{1}}{2}>0$ thus implies $|E(\Gamma)|<n$, which if $\Gamma$ is to be connected means it must be a tree.

So if you're searching for a counterexample, you can narrow things down to trees with maximum degree 3. From here though, I'm not sure. Is there a tree of max degree 3 with two vertices of max degree and $\lambda_{1}<2$? Maybe, but I'm not sure, nor do I know how to prove it can't happen.

$\textbf{Edit:}$ you might check section 3 of this: https://math.mit.edu/~apost/courses/18.204_2018/DynkinDiagrams.pdf.

Answer 2

Inspired by Austin80's answer (but self-contained):

Since we have $q_\Gamma(\mathbf x) = {\mathbf x}^{\mathsf T}B \mathbf x$ where $B = I - \frac12A$ and $A$ is the adjacency matrix of $G$, $q_\Gamma$ is positive definite if and only if the largest eigenvalue of $A$ is less than $2$.

We can write down the problem of finding the largest eigenvalue of a matrix $A$ as an optimization problem: $$ \lambda_1 = \sup \left\{\frac{\mathbf x^{\mathsf T} A \mathbf x}{\mathbf x^{\mathsf T}\mathbf x} : \mathbf x \ne \mathbf 0\right\}. $$ To show that $\lambda_1 \ge 2$, it's enough to find some vector $\mathbf x$ for which we get $\frac{\mathbf x^{\mathsf T} A \mathbf x}{\mathbf x^{\mathsf T}\mathbf x} \ge 2$.

Suppose $v_1, v_2$ are two vertices of degree at least $3$ in the same connected component of $G$. Let $v_1, u_1, u_2, \dots, u_k, v_2$ be a $v_1, v_2$-path, and let $w_1, w_2, w_3, w_4$ be two more neighbors of $v_1$ and two more neighbors of $v_2$ (distinct from $u_1$ and $u_k$).

Define $\mathbf x$ to have a component of $1$ in entries corresponding to vertices $v_1, u_1, \dots, u_k, v_2$, a component of $\frac12$ in entries corresponding to $w_1, w_2, w_3, w_4$, and $0$ everywhere else. Then:

• $\mathbf x^{\mathsf T} \mathbf x = k+3$: the $k+2$ vertices of weight $1$ contribute $k+2$, and the $4$ vertices of weight $\frac12$ contribute $4 \cdot \frac14 = 1$.
• $\mathbf x^{\mathsf T} A \mathbf x \ge 2k+6$: the $k+1$ edges with both endpoints of weight $1$ contribute $2(k+1)$, and the $4$ edges with a weight-$1$ and weight-$\frac12$ endpoint contribute $2 \cdot 4 \cdot \frac12 = 4$. ($\mathbf x^{\mathsf T} A \mathbf x$ might be larger if there are other edges between these vertices that we don't know about).

Therefore $\lambda_1 \ge \frac{\mathbf x^{\mathsf T} A \mathbf x}{\mathbf x^{\mathsf T}\mathbf x} \ge 2$ and $q_\Gamma$ is not positive definite (positive semidefinite at best).

The vector $\mathbf x$ may seem arbitrary, but here is where it comes from. The subgraph corresponding to the $u,v,w$ vertices we found is a tree with largest eigenvalue $2$, and $\mathbf x$ is the corresponding eigenvector. In general, the largest eigenvalue of a subgraph is going to give us a lower bound for the largest eigenvalue of a graph, by a similar argument.

We could avoid talking about the adjacency matrix $A$ entirely; taking the vector $\mathbf x$ above, we could just directly argue that $q_\Gamma(\mathbf x) \le 0$. This would be shorter, but less generalizable.