I understand that if k is odd and G is k-regular, then each vertex must have odd degree. I am having trouble understanding how to incorporate the edge-connectivity.
(This is my first undergraduate graph theory class, so a simple explanation would be helpful.)
Thanks!
In fact, $k$ could be even and odd and theorem holds.
We can use Tutte's theorem to prove the result.
Let $S \subset V(G)$, and $odd(G/S)$ the number of odd components in $G-S$.
Then the number of edges out of $S$ is at most $|S|*k$. Now consider an odd component $O$ in $G-S$, we have: $$ k*|O|=\sum_{v \in V(O)}deg(v) = 2|In|+|Out| $$ Here $|Out|$ denotes the number of edges with only one end in $O$ and $In$ denotes the number of edges with both end in $O$. Now because $|O|$ is odd so $k$ has the same parity as $|Out|$.
Edit: Now $|Out| \geq k-1$, so $|Out| \geq k$(here we use the fact that $|Out|$ and $k$ has the same parity).
to Now $|Out| \geq k-1$, so $|Out| \geq k$(here we use the fact that $|Out|$ and $k$ has the same parity). So thanks to the comment due to @Misha, we realized that $|Out| \geq k-1$ is true if $k$ is odd. Otherwise $|Out|$ could be even and hence equals to $0$ and then the argument breaks.
Now the number of edges with one end in an odd component and one end in $S$ is at least $k|odd(G-S)|$ which is also less than or equals to $|S|*k$. So $|S| \geq |odd(G-S)|$. So by Tutte's theorem the graph has a perfect matching.