Edge coloring of a $k$-regular bipartite graph Let $G$ be a $k$-regular bipartite graph. I want to prove that I can color the edges of $G$ with at most $k$ colors. I want to do this without using König's theorem.
Ideally I would like to prove this constructively but I can't figure out how because I am sure about the structure of $G$. I was under the impression that all of the components of $G$ are isomorphic to $K_{k,k}$, which I know how to color. However, this is false.
Anywho, if anyone can give me any tips, I would greatly appreciate it.
 A: We start with the following 

Proposition 1. A graph $G$ is $k$-edge colourable if and only if the edge set of $G$ can be decomposed into (at most) $k$ matchings. 

The above would follow immediately once you recognize that each color class of edges corresponds to a matching. With this new terminology at hand, we can rewrite the given statement equivalently as

Theorem 2 (Hall's theorem for bipartite regular graphs). Suppose $G$ is a bipartite $k$-regular graph. Then the edges of $G$ can be decomposed into $k$ (perfect) matchings. 

This is a standard "big" theorem in graph theory. So any justification of the OP's statement must either quote Hall's theorem directly, or must reinvent the wheel and prove Hall's theorem implicitly. I prefer the first approach over the second. See the wikipedia page for more details on Hall's theorem.

Note: Often, textbooks prove the seemingly weaker statement:

Theorem 3 (Hall's theorem for bipartite regular graphs, version II). Every bipartite regular graph contain a perfect matching. 

But the two versions are, in fact, equivalent. To go from Theorem 3 to Theorem 2, keep stripping off a perfect matching from the graph repeatedly $k$ times, until the graph becomes empty. 
