13
$\begingroup$

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 ?

  • 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.2012-07-02
  • 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.2012-07-02
  • 1
    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.2014-10-26
  • 0
    I second bof's comment at 'Oct 26 '14 at 0:28': Frieze's proof(-sketch) is *correct*, because 'graph' means 'multigraph' in the document in question.2018-02-27

3 Answers 3