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.

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

share|improve this question
    
It's not clear in your statement of the problem whether or not every vertex is to still have the same degree. –  Tim Duff 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? –  Tim Duff 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
1  
@TimDuff Note that the question does not require the $k$ matchings to be perfect. –  Erick Wong Jul 7 '12 at 9:07
add comment

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$)

share|improve this answer
    
Could you maybe do this more rigorously? –  Aria Fitzpatrick Jul 7 '12 at 15:17
add comment

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$.

share|improve this answer
add comment

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$.

Example of $G \setminus \{uv\}$

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.

Example of $P$

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.

Example of swapping edge colours in $P$

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.

Example of the final result

share|improve this answer
add comment

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.