0
$\begingroup$

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.

  • 0
    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.2011-11-20

1 Answers 1

4

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.

  • 0
    I do not mind using Hall's marriage theorem. This is really neat. Thanks a lot.2011-12-14