Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A theorem of König says that

Any bipartite graph $G$ has an edge-coloring with $\Delta(G)$ (maximal degree) colors.

This document proves it on page 4 by:

  1. Proving the theorem for regular bipartite graphs;
  2. Claiming that if $G$ bipartite, but not $\Delta(G)$-regular, we can add edges to get a $\Delta(G)$-regular bipartite graph.

However, there seem to be two problems with the second point:

  • A regular bipartite graph has the same number of vertices in the two partions. So we need to add vertices also.
  • I'm not sure that it is always possible to add edges to get a $\Delta$-regular bipartite graph, even if we have the same number of vertices. See the figure below. B and E both have degree two, but we cannot make them degree 3

Am I right ? Is there a way to correct that ?

share|improve this question
1  
A good way to do this is to prove that any bipartite graph has a matching that covers each vertex of maximum degree. (The proof of this is got using the ideas you'd use to prove Koenig's theorem. It's not trivial.) As your example shows, you cannot always make a bipartite graph regular by adding edges. –  Chris Godsil Jul 2 '12 at 14:04
3  
Is there is any problem with having multiple edges in this proof? If not you can just add another edge between E and B. Similarly, it is possible to add isolated vertices to the graph (to get the same number of vertices in each set) before adding the edges and the colouring of the regular graph thus formed will transfer back to the original graph. –  jp26 Jul 2 '12 at 14:07
    
The document you quote starts off by saying "We assume in this chapter that $G$ has no loops." Evidently, the discussion is not restricted to simple graphs, multiple edges are allowed. There is no good reason to restrict the discussion to simple graphs; the theorem is true for graphs with multiple edges, and restricting it to simple graphs does not make the proof easier. Of course you still have to add vertices to get the same number of vertices on both sides. –  bof Oct 26 at 0:28

1 Answer 1

You have to be allowed to add vertices. In that case it is provable by induction on the number of edges:
Assume G' := G \ e is a Subgraph of some Δ'-regular bipartite Graph K'.
1. Case Δ = Δ' + 1:
K = K' plus e plus an edge for every two other vertices.
2. Case e is in K':
K = K'
3. Case e is not in K':
Let e = (a,b). Because we do not increase Δ, there must be edges in K' \ G' f = (a,c) and g = (b,d). Make a copy of K' =: K'' and join them. Remove f, g and their copies. Connect e, the copy of e, (a,c'), (b,d'), (a',c), (b',d). Here a' is the copy of a etc.. This gives K with all the right edges and degrees.

We can start the induction at 0 edges, and take as K an edgeless bipartite Graph with partitions of the same size, so that it includes G.

Case 3 can done sometimes without the doubling of the graph, but not always. Your example is a case, which can be solved by doubling the graph. Adding vertices is also no problem for your point 1, because it is independent of the number of vertices.

share|improve this answer

Your Answer

 
discard

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.