GRAPHS WITH TWO MAIN AND TWO PLAIN EIGENVALUES

NEW

Problem: Reconstructed statement: let $\Gamma$ be a finite simple connected graph with adjacency matrix $A$. An eigenvalue is main if its eigenspace is not orthogonal to the all-ones vector ${\bf j}$, and plain if its eigenspace contains a nonzero vector orthogonal to ${\bf j}$. A graph is $t$-valenced if it has exactly $t$ distinct vertex degrees. With Seidel matrix $S=J-I-2A$, $\Gamma$ is strong if

The conjecture asks for a universal positive integer $C$ such that every connected $t$-valenced graph with exactly two main and exactly two plain eigenvalues is strong whenever $t\ge C$.

Result: The conjecture is true. In fact one may take

Proof. Let the two plain eigenvalues be $\theta,\tau$. Put ${\bf d}=A{\bf j}$, the degree vector.

Since $A$ has exactly two main eigenvalues, the $A$-cyclic space generated by ${\bf j}$ is two-dimensional. Hence

is $A$-invariant and has dimension $2$. Because $A$ is symmetric, $L^\perp$ is also $A$-invariant. Every eigenvector in $L^\perp$ is orthogonal to ${\bf j}$, so its eigenvalue is plain. Thus the restriction of $A$ to $L^\perp$ has only the eigenvalues $\theta,\tau$. Therefore

vanishes on $L^\perp$, and since $B$ is symmetric its image lies in $L$. Hence for some real $\alpha,\beta,\gamma$,

Taking diagonal entries at a vertex $v$ of degree $k=d_v$, and using $A_{vv}=0$, $(A^2)_{vv}=k$, gives

Thus every vertex degree is a root of the quadratic

If $\Gamma$ has at least three distinct degrees, this polynomial is identically zero. Hence

so

Equivalently,

Now compute

Substituting the displayed formula for $A^2$, the mixed degree terms cancel, yielding

Since $A=(J-I-S)/2$, this lies in $\operatorname{span}_{\mathbb R}\{S,I,J\}$. Therefore $\Gamma$ is strong.

Thus every connected $t$-valenced graph with two main and two plain eigenvalues is strong whenever $t\ge3$, proving the conjecture.

Verification audit: the proof uses exactly the paper’s definitions of $t$-valenced, main/plain eigenvalue, and strong graph. Connectedness is not strengthened; the argument only uses finite simple undirected adjacency matrices. The possibility that an eigenvalue is both main and plain is allowed. The conclusion is precisely the conjectured conclusion, with the explicit universal constant $C=3$.

Citation: Definitions and conjecture: Sakander Hayat, Muhammad Javaid, Jack H. Koolen, “Graphs with two main and two plain eigenvalues,” arXiv:1612.00589. The proof above is self-contained.