Consider two regular graphs $G_1$ and $G_2$ of degrees $d_1$ and $d_2$, respectively. I would like to prove that the Cartesian product $G_1 \square G_2$ is regular of degree $d_1 + d_2$.
Currently I have a proof that revolves around the following facts:
The adjacency matrix of $G_1 \square G_2$ is $A_{G_1 \square G_2} = A_{G_1}\otimes I_{n_2} + I_{n_1} \otimes A_{G_2}$ where $A_{G_i}$ is the adjacency matrix of $G_i$ and $n_i$ is the number of vertices of $G_i$.
The eigenvalues of the Kronecker product of two matrices $B$ and $C$ are all the possible products of eigenvalues of one eigenvalue of $B$ with one eigenvalue of $C$.
A graph is $d$-regular if and only if $\mathbf{1} = (1,\dotsc,1)^T$ is an eigenvector of its adjacency matrix, in which case the corresponding eigenvalue is $d$.
A graph is $d$-regular if and only if the maximal eigenvalue of its adjacency matrix is $d$.
On the other hand, I would like to know if there is a more elementary (but not longer) proof.
There's a far more elementary proof, using just the definition of the Cartesian product. Let $G_1 = (V_1, E_1)$ be $d_1$-regular and let $G_2 = (V_2, E_2)$ be $d_2$-regular. Recall that the Cartesian product is defined as $ G_1 \square G_2 = (V_1 \times V_2, E) $ where $\times$ is the ordinary Cartesian product (on sets) and $$E = \big\{ (v_1, v_2) (u_1, u_2) \,\big|\, (v_1 = u_1 \text{ and } v_2 u_2 \in E_2) \text{ or } (v_2 = u_2 \text{ and } v_1 u_1 \in E_1 )\big\} .$$ For a fixed $(v_1, v_2) \in V(G_1 \square G_2)$, there are $d_2$ neighbors $(u_1, u_2)$ such that $v_1 = u_1$ and $v_2 u_2 \in E_2$ and there are $d_1$ neighbors $(u_1, u_2)$ such that $v_2 = u_2$ and $v_1 u_1 \in E_1$. Assuming the graphs are simple (no loops, etc.), we've counted each neighbor of $(v_1, v_2)$ exactly once and gotten $d_1 + d_2$ of them, not matter what $(v_1, v_2)$ was. Thus $G_1 \square G_2$ is $(d_1 + d_2)$-regular. (The detail here might be a bit overbearing, and could definitely be pared down.)