bipartite simple graph matching-proof

Prove that if $G$ is a bipartite simple graph and every vertex has the same degree $k$, then the edges of $G$ can be partitioned into $k$ matchings. Can we then prove the same if every vertex has degree $\le k$?

-
It's not clear in your statement of the problem whether or not every vertex is to still have the same degree. – user17794 Jul 7 '12 at 8:27
The second bit asks whether the same can be proven if every vertex has degree AT MOST $k$ rather than $=k$. Does that answer your question? – Aria Fitzpatrick Jul 7 '12 at 8:31
No. Does every vertex have the same degree or may vertices have different degrees? – user17794 Jul 7 '12 at 8:48
The first proof requires that all vertices have deg=k, while the second doesn't(but has a max cap on deg=k). – Aria Fitzpatrick Jul 7 '12 at 8:59
@TimDuff Note that the question does not require the $k$ matchings to be perfect. – Erick Wong Jul 7 '12 at 9:07

3 Answers

The "big stick" route is via iterative application of Hall's Marriage Theorem, which for our purposes tells us that a regular bipartite graph has a perfect matching (restricted to regular bipartite graphs, the proof of this is not too hard either).

Then given $k$-regular bipartite $G=(V_{1}\uplus V_{2},E)$ we can find a perfect matching $M \subseteq E$. Let $G'=(V_{1}\uplus V_{2}, E\setminus M)$. $G'$ is clearly a $(k-1)$-regular bipartite graph, hence we can apply Hall's theorem again, et cetera.

You could also go the other way, and give an inductive proof. The base case of $k=1$ is obvious, then with the assumption that $k=p-1$ gives us a $(p-1)$-matching it's relatively straight forward to show that for $k=p$ you can find a perfect matching, then apply the inductive assumption for the graph without that matching, though you're really just showing the special case of Hall's theorem again to prove that you can get the first perfect matching.

For the second part you should be able to do basically the same with Hall's theorem. First discard any degree zero vertices, then take a matching which covers the smaller side, remove this and iterate. A simple contradiction argument shows that you can do this at most $k$ times. (Assume you do it $k$ times and there's some edge left over, but it can't be part of any of the $k$ previous matchings, then at least one of its end points must have an edge in all the matchings, and hence must have degree greater than $k$)

-
Could you maybe do this more rigorously? – Aria Fitzpatrick Jul 7 '12 at 15:17

A bipartite graph $G$ with degree bounded above by $k$ can be extended (as necessary by adding both vertices and edges) to a regular bipartite graph $H$ of degree $k$. Partitioning the edges of $H$ into $k$ perfect matchings then induces a partition of edges of $G$ into $k$ (not necessarily perfect) matchings.

Added: It would probably be in keeping with the problem to phrase the conclusion as partitioning $G$ into at most $k$ matchings, since the above construction may produce matchings in $H$ that miss $G$.

-

I'll give a self-contained proof; I "borrowed" this proof from Theorem 7.6.3 in A Textbook of Graph Theory by Balakrishnan and Ranganathan.

Theorem (König): Let $G$ be a bipartite graph with maximum degree $\Delta$. Then $G$ can be assigned a proper edge colouring using $\Delta$ colours.

Proof: We proceed by induction on the number of edges $m$ (having fixed the vertex set, and vertex bipartition). The theorem is true for $m=1$. Now assume $m>1$.

Let $uv$ be an edge in $G$. By the inductive hypothesis, $G \setminus \{uv\}$ can be properly edge coloured using $\Delta$ colours. An example is given below for $\Delta=3$.

In this colouring of $G \setminus \{uv\}$:

• Let $i$ be a colour not used for an edge with an endpoint $u$ in $G \setminus \{uv\}$.
• Let $j$ be a colour not used for an edge with an endpoint $v$ in $G \setminus \{uv\}$.

Note: both $i$ and $j$ exist, since the degrees of $u$ and $v$ in $G \setminus \{uv\}$ are at most $\Delta-1$.

We can assume $u$ is the endpoint of an $j$-coloured edge, otherwise, we can assign $uv$ the colour $j$, and we are done.

Let $P$ be the maximum-length path starting at $u$ following edges of colours $j$ and $i$ alternatingly. In the above example, we take $i=\text{blue}$ and $j=\text{red}$, so $P$ is the path depicted below.

Importantly, $P$ cannot have $v$ as a vertex; this would imply one of the following:

• If $v$ were an internal vertex of $P$, then $v$ is an endpoint of an $j$-coloured edge, giving a contradiction.

• If $v$ were a terminal vertex of $P$, then either $u$ and $v$ belong to the same part (contradicting that $G$ is bipartite) or $v$ is an endpoint of an $j$-coloured edge, giving a contradiction.

If we swap the colours $i$ and $j$ in $P$, we obtain a new proper edge colouring of $G \setminus \{uv\}$ using $\Delta$ colours. (It is indeed proper, since $P$ is of maximum-length.) In the above example, we obtain the following modified colouring.

However, this time, both $u$ and $v$ are not the endpoint of an $j$-coloured edge, so we can add back in the edge $uv$ and colour it $j$, thereby obtaining a proper edge colouring of $G$ using $\Delta$ colours. In our running example, the final result is the following.

-