How can I prove that $MM^t=A+kI$ for incidence matrix $M$ and adjacency matrix $A$ of a $k$-regular graph with $n$ vertices?
It is easy to see that $MM^t$ is an $n\times n$-matrix (like $A$), likewise it is easy to see that it has all $k$'s on its diagonal. But after this I'm stuck. My linear algebra is pretty weak so I may be missing something really obvious.
This follows from intuitively thinking of the $i,j$-entry of $M M^t$ as listing the number of walks from $v_i$ to $v_j$ that include one edge.
If you're not convinced, or want to see a more complete argument, let $G = ( V , E )$ be a graph.
Suppose $v_i v_j$ are adjacent. Then, there's a unique edge $e_m = v_i v_j$. So if the $i,j$-entry of $A$ is $1$, then there is exactly one $m$ such that the $i,m$-entry of $M$ is $1$ and the $m,j$-entry of $M^t$ is $1$. So $(MM^t)_{ij} = \sum_{m=1}^n M_{im}M_{jm} = 1$. And if $v_i v_j$ is not an edge, no such $e_m$ exists, and $(M M^t)_{ij} = \sum_{m=1}^n M_{im} M_{jm}$, and at least one of $M_{im}$ or $M_{jm}$ is $0$.
But we've implicitly assumed above that $i \ne j$. What is it along the diagonal (i.e. when $i=j$)? Well, we have $d(v_i)$ edges incident with $v_i$, so there are $d(v_i)$ many $m$ such that $v_i e_m v_i$ is a walk. Since $d(v_i) = k$ (since the graph is $k$-regular), the diagonal of the matrix consists of $k$.