Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 4 down vote accepted

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.

share|cite|improve this answer
I do not mind using Hall's marriage theorem. This is really neat. Thanks a lot. – echoone Dec 14 '11 at 8:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.