3 added 20 characters in body

I believe the answer is yes and that this might be found somewhere in the literature on the graph reconstruction problem.

Let me denote the characteristic polynomial of the graph $G$ as $\phi(G,x)$ and let its cofactors be $\phi_{ij}(G,x)$. In the paper "Walk Generating Functions, Christoffel-Darboux Identities and the Adjacency Matrix of a Graph", C.D. Godsil proves the following lemma (5.2) which is a graph theoretic analogue to the Christoffel-Darboux formula for orthogonal polynomials, the identity can be proven by purely combinatorial means:

Let $V(G)=\{1,2,\dots,n\}$ be the vertices of $G$, then for any pair $i,j$ one has $$\sum_{k\in V(G)}\phi_{ik}(G,x)\phi_{jk}(G,y)=\frac{\phi_{ij}(G,x)\phi(G,y)-\phi_{ij}(G,y)\phi(G,x)}{y-x}.$$

Taking $i=j$ one obtains $$\sum_{k\in V(G)}\phi_{ik}(G,x)\phi_{ik}(G,y)=\frac{\phi_{ii}(G,x)\phi(G,y)-\phi_{ii}(G,y)\phi(G,x)}{y-x}.$$

If there was a graph with a complex eigenvalue then pick such a graph with the smallest number of vertices. Let the eigenvalue be $\eta$, and substitute in our identity $x=\eta, y=\bar{\eta}$. We see that the RHS vanishes and so must $\sum_{k\in V(G)}|\phi_{ik}(G,\eta)|^2$, so in particular $\phi_{ii}(G,\eta)=0$. But $\phi_{ii}(G,x)=\phi(G/i,x)$ and so $G/i$ would then be a graph with one less vertex having $\eta$ as a rootan eigenvalue, contradicting our minimality assumption.

2 added 498 characters in body

I believe the answer is yes and that this might be found somewhere in the literature on the graph reconstruction problem.

Let me denote the characteristic polynomial of the graph $G$ as $\phi(G,x)$ and let its cofactors be $\phi_{ij}(G,x)$. In the paper "Walk Generating Functions, Christoffel-Darboux Identities and the Adjacency Matrix of a Graph", C.D. Godsil proves the following lemma (5.2) which is a graph theoretic analogue to the Christoffel-Darboux formula for orthogonal polynomials, the identity can be proven by purely combinatorial means:

Let $V(G)=\{1,2,\dots,n\}$ be the vertices of $G$, then for any pair $i,j$ one has $$\sum_{k\in V(G)}\phi_{ik}(G,x)\phi_{jk}(G,y)=\frac{\phi_{ij}(G,x)\phi(G,y)-\phi_{ij}(G,y)\phi(G,x)}{y-x}.$$

He remarks later that this imediately implies that

Taking $i=j$ one obtains $$\sum_{k\in V(G)}\phi_{ik}(G,x)\phi_{ik}(G,y)=\frac{\phi_{ii}(G,x)\phi(G,y)-\phi_{ii}(G,y)\phi(G,x)}{y-x}.$$

If there was a graph with a complex eigenvalue then pick such a graph with the roots smallest number of vertices. Let the eigenvalue be $\phi(G,x)$ are all real \eta$, and substitute in our identity$x=\eta, y=\bar{\eta}$. We see that the identity can RHS vanishes and so must$\sum_{k\in V(G)}|\phi_{ik}(G,\eta)|^2$, so in particular$\phi_{ii}(G,\eta)=0$. But$\phi_{ii}(G,x)=\phi(G/i,x)$would then be proven by purely combinatorial meansa graph with one less vertex having$\eta$as a root, contradicting our minimality assumption. 1 I believe the answer is yes and that this might be found somewhere in the literature on the graph reconstruction problem. Let me denote the characteristic polynomial of the graph$G$as$\phi(G,x)$and let its cofactors be$\phi_{ij}(G,x)$. In the paper "Walk Generating Functions, Christoffel-Darboux Identities and the Adjacency Matrix of a Graph", C.D. Godsil proves the following lemma (5.2) which is a graph theoretic analogue to the Christoffel-Darboux formula for orthogonal polynomials: Let$V(G)=\{1,2,\dots,n\}$be the vertices of$G$, then for any pair$i,j$one has $$\sum_{k\in V(G)}\phi_{ik}(G,x)\phi_{jk}(G,y)=\frac{\phi_{ij}(G,x)\phi(G,y)-\phi_{ij}(G,y)\phi(G,x)}{y-x}.$$ He remarks later that this imediately implies that the roots of$\phi(G,x)\$ are all real and that the identity can be proven by purely combinatorial means.