16
$\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 ?

  • 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

3

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.

  • 0
    in the 3r$d$ case if you add both `e` and `(a,c')` the degree of `a` will increase. Probably you need to add only `(b,d')` and `(b',d)` .. Do I get it right?2015-04-17
1

This is ancient history but I thought I'd post a quick alternative fix to the multiple-edge issue, in case this was useful to anyone (I taught this recently and came across this exact problem).

To begin with add vertices of degree $0$ so the graph has the same number of vertices on each side.

Now proceed as in the original proof; only if you were going to add an edge $xy$ there, instead add an entire new $K_{\Delta(G),\Delta(G)}$ with one of its edges $ab$ removed, and then also add edges $xb$ and $ya$.

0

I'm wondering if this is an appropriate solution, I'd love some feedback:

Let $G$ be a bipartite graph with $n>2$ vertices and assume that $X'(G) \lt \Delta(G)$. Recognize that the bipartite graph with $n$ vertices which contains the smallest possible $\Delta(G)$ is a simple path $P:=(v_1,e_1,v_2,e_2,..,e_{n-1},v_n)$ where each partition of the graph contains every other vertex. It is clear that in this case, $\Delta(G)=2$ which is a contradiction because a proper coloring which would correspond to $X'(G)=1$ is impossible in a connected graph with more than 2 vertices. Also, notice that a coloring of 2 is exactly $X'(G) =\Delta(G)=2$ and any coloring which uses more than 2 colors is not minimized.

On the other hand, the bipartite graph with $n$ vertices which contains a vertex which has the highest possible $\Delta(G)$ is the complete bipartite graph $K_{1,n-1}$. Here, the lone vertex in a partition of its own has $\Delta(G)=n-1$. Here we can see that a coloring $X'(G) \lt n-1$ is impossible because there are exactly $n-1$ incident edge. Notice that a coloring of exactly $X'(G) = \Delta(G)=n-1$ is the only proper coloring of $G$ and any color set which has more than $n-1$ elements is nonsensical (more colors than edges).

Therefore any bipartite graph with $n$>2 vertices has a chromatic edge coloring of $X'(G) = \Delta(G)$.