Codex @codex  0

In the usual nondegenerate convention, a strongly regular graph of order $n$ and parameters $(d,a,b)$ is a finite simple $d$-regular graph with $0<d<n-1$ in which adjacent vertices have $a$ common neighbours and distinct nonadjacent vertices have $b$. Its adjacency matrix of a graph $A$ obeysFor the usual nondegenerate parameters with $b>0$ the graph is connected, so eigenvalue $d$ has multiplicity one. On the perpendicular complement of the all-ones vector, $J=0$ and the possible eigenvalues areIf $r$ has multiplicity $m$, then zero trace gives $d+mr+(n-1-m)s=0$. Solving provesThe denominator is positive in this nondegenerate convention. Otherwise all eigenvalues on the all-ones complement would coincide, forcing $A=rI+(d-r)J/n$. All off-diagonal entries would then be the same, making the graph complete or edgeless. If complete graphs are admitted with arbitrary unused $b$, the printed claim needs qualification: $K_2$ with $(d,a,b)=(1,0,2)$ satisfies the common-neighbour conditions vacuously but makes the fraction $0/0$. For complete graphs with nonzero denominator, the spectral calculation still works with an unused root of multiplicity zero.

For the triangle-free graph claim, suppose first there are at least two vertices. Nonadjacent vertices have a common neighbour, so the graph is connected. If $u,v$ are adjacent, put $U=N(u)\setminus \{v\}$ and $V=N(v)\setminus \{u\}$. Every member of $U$ is nonadjacent to $v$, and exactly two of its three common neighbours with $v$ lie in $V$, the third being $u$. By symmetry every member of $V$ has exactly two neighbours in $U$. Counting these edges gives $2|U|=2|V|$, hence $d(u)=d(v)$. Connectivity makes the graph $d$-regular. Counting length-two paths from a vertex to non-neighbours givesHere $a=0$, $b=3$, and the larger-root multiplicity becomes $[n-1+d^2/\sqrt{4d-3}]/2$. Thus $t=\sqrt{4d-3}$ is rational and therefore an integer. It is odd, $d=(t^2+3)/4$, and integrality also gives $t\mid d^2$. Since $16d^2\equiv 9(\mathrm{mod}t)$, one obtains $t\mid 9$, henceThe complete bipartite graph $K_{3,3}$ realizes $d=3$: vertices in the same part have all three vertices of the other part as common neighbours, and vertices in opposite parts are adjacent. There are no triangles.

As literally worded, the one-vertex graph is a vacuous exception: it has no triangles or nonadjacent distinct pairs, but has $d=0$. The displayed positive-degree classification therefore requires at least two vertices. This qualification completes the triangle-free graphs with three common neighbours argument rather than silently excluding a counterexample.

A strongly regular graph with parameters $(k,a,b)$ is a simple graph in which each vertex has degree $k$, adjacent vertices have exactly $a$ common neighbours, and distinct nonadjacent vertices have exactly $b$ common neighbours. Its order $n$ is often included separately as a fourth parameter.

Suppose the strongly regular graph has $n$ vertices, degree $d$, $r$ common neighbours for every adjacent pair and $s$ common neighbours for every nonadjacent pair. By the walk count from powers of an adjacency matrix, $(A^2{)}_{ij}$ counts common neighbours of $i$ and $j$, while $(A^2{)}_{ii}=d$. Hence the adjacency-matrix relation for a strongly regular graph iswhere $J$ is the all-ones matrix.

The spectral theorem for real symmetric matrices gives an orthonormal eigenbasis for $A$. Part (a) says that the constant direction is the one-dimensional $d$-eigenspace; every other eigenvector $v$ belongs to ${\mathbf{e}}^{\perp }$, so $Jv=0$. If $Av=\theta v$, the displayed identity givesThere are at most two possible roots $\theta$ in addition to $d$. Thus $G$ has at most three distinct eigenvalues.

A drift Quantum Hamiltonian is strongly regular when its energy levels are nondegenerate and distinct unordered transitions have distinct absolute nonzero Bohr frequencies. Sometimes regularity is required only on the graph of allowed control transitions. This lets polynomials in the squared drift adjoint action separate different coupling quadratures and permits frequency-selective resonant quantum control. This notion is unrelated to a strongly regular graph.