# 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.

-
You don't want to use König's theorem, fine. So what can you use? – Srivatsan Nov 20 '11 at 20:55
Well, I would like to prove this without relying on any big theorem. I have a funny feeling though that proving this will pretty much yield a reproduction of the proof of König's theorem. – echoone Nov 20 '11 at 21:01

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.

-
I do not mind using Hall's marriage theorem. This is really neat. Thanks a lot. – echoone Dec 14 '11 at 8:18