= Solution
Let $A$ be the <adjacency matrix of a graph>, $J$ the all-ones <matrix> and $\mathbf1$ the all-ones vector. Counting two-step walks gives
$$
A^2=(k-b)I+(a-b)A+bJ,\qquad A\mathbf1=k\mathbf1.
$$
Because $b\geq1$, any two nonadjacent vertices have a common neighbour, so the graph is connected. The <eigenvalue> $k$ is simple: for a real <eigenvector> at $k$, a maximal entry and the averaging equation force its neighbours, and then every vertex, to have the same value. Since $A$ is real symmetric, its other <eigenvectors> lie in $\mathbf1^\perp$, where $J$ vanishes. Their <eigenvalues> are therefore
$$
r,s=\frac{a-b\pm d}{2},\qquad d=\sqrt{(a-b)^2+4(k-b)}.
$$
Here $d>0$ for the present incomplete connected graph. Indeed $k\geq b$; if $d=0$, then $k=b=a$, which conflicts with $a\leq k-1$ for an edge. If $r,s$ have multiplicities $m_r,m_s$, dimension and zero trace give $m_r+m_s=n-1$ and $k+m_rr+m_ss=0$. Thus
$$
\boxed{m_r=\frac12\left(n-1+\frac{(n-1)(b-a)-2k}{d}\right),\qquad
m_s=\frac12\left(n-1-\frac{(n-1)(b-a)-2k}{d}\right)}.
$$
These are dimensions of <eigenspaces>, hence integers. A multiplicity may be zero; that does not affect the conclusion.
Back to article page
