Let G be a (2d-1) regular graph, and $(X_1,X_2)$ be a partition of vertices of G s.t. if $v\in X_i$, then $|N(v) \cap X_i|=d$. Prove that one is an eigenvalue of the adjacency matrix of G.
Since is 2−1 regular, then every vertex of $G$ is adjacent to $2d-1$ other vertices, so each row of its adjacency matrix $A$ will have $2d-1$ $1$’s and $n-2d+1$ $0$’s. Let
$$A=\pmatrix{a_{11}&a_{12}&\dots&a_{1n}\\ a_{21}&a_{22}&\dots&a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n1}&a_{n2}&\dots&a_{nn}}\;,$$
Additionally, since G is a 2d-1 regular graph, meaning that degree of $v\in X_1$ is 2d-1, making v have (d-1) neighbors in $X_2$; since $|N(v) \cap X_1|=d$ this means v has d neighbors in $X_1$ (vice versa). I am stuck here and not sure how to proceed to get the eigenvalue 1. Any help is appeciated.
Let $n\ge1$ be the number of vertices in $G$ and consider the linear maps $\Bbb R^n\to \Bbb R$, defined as follows for $\mathbf x =(x_1,\ldots, x_n)\in \Bbb R^n$: $$\begin{align}\phi(\mathbf x)&=\sum_{j\in X_1}x_j,\\ \psi(\mathbf x)&=\sum_{j\in X_2}x_j,\\ \delta(\mathbf x)&=\phi(\mathbf x)-\psi(\mathbf x).\end{align}$$ Note that $\delta$ is not identically zero (e.g., $\delta(\mathbf e_j)=\pm1$, depending on whether $j\in X_1$ or $j\in X_2$), hence $\ker\delta$ is a proper subspace of $\Bbb R^n$.
As each vertex $v\in X_1$ has $d$ neighbours in $X_1$ and $d-1$ neighbours in $X_2$, and similarly for $v\in X_2$, we see that $$\begin{aligned} \phi(A\mathbf x)&=d\phi(\mathbf x)+(d-1)\psi(\mathbf x),\\\psi(A\mathbf x)&=(d-1)\phi(\mathbf x)+d\psi(\mathbf x),\end{aligned}$$ and therefore $$ \delta(A\mathbf x)=\delta(\mathbf x).$$ As $A$ is symmetric, there exists a basis of eigenvectors and all eigenvalues are real. As $\ker \delta$ is a proper subspace, there exists at least one eigenvector $\mathbf x$ for which $\mathbf x\notin \ker\delta$. For its corresponding eigenvalue $\lambda$, we have $$ \lambda=\frac{\delta(A\mathbf x)}{\delta(\mathbf x)}=1.$$