5
$\begingroup$

I need to prove following lemma:

Any bipartite graph has a matching that covers each vertex of maximum degree

Any help will be appreciated.

$\endgroup$
4
  • $\begingroup$ I don't understand the statement, can you be more precise? $\endgroup$ – Igor Rivin Jan 14 '14 at 22:07
  • $\begingroup$ @IgorRivin What is not clear? $\endgroup$ – bof Jan 15 '14 at 6:48
  • $\begingroup$ For example, if the graph is regular, are you saying that it has a perfect matching? $\endgroup$ – Igor Rivin Jan 15 '14 at 13:35
  • 1
    $\begingroup$ The keyword is 'bipartite'. If it is regular and bipartite, it has a perfect matching. $\endgroup$ – Leen Droogendijk Jan 15 '14 at 14:51
5
$\begingroup$

Let $G$ be our bipartite graph with bipartition $X,Y$ and let the maximum degree be $k$. Let $S_X$ be the set containing exactly all vertices of degree $k$ in $X$ and $S_Y$ the set containing all vertices of degree $k$ in $Y$. Let $A\subset S_X$ and $N(A)$ be the neighbours of $A$.

Exactly $k|A|$ edges are leaving vertices of $A$, so $k|A|$ vertices must be arriving at vertices of $N(A)$. Since each vertex of $N(A)$ has degree at most $k$, $N(A)$ must have at least $|A$| vertices. So Hall's condition is satisfied and there is a matching $M_X$ of $S_X$. In the same way we find a matching $M_Y$ of $S_Y$.

Now let $G'$ be the subgraph that consists of exactly the edges of $M_X$ and $M_Y$. Let $T_X$ be the vertices of $X$ that are matched using $M_Y$ and $T_Y$ vertices that are matched using $M_X$ (draw a picture or you will get confused!).

Take an arbitrary vertex $v$ in $S_Y-T_Y$. It has degree 1 so it must start a path. This path must start with an edge of $M_Y$. The next vertex on that path, $w$, will certainly be in $T_X$. If $w$ is not in $S_X$ the path ends (we just traveled an edge of $M_Y$ and we can only continue along an edge of $M_X$ if $w$ is in $S_X$). If $w$ is in $S_X$ we continue along an edge of $M_X$ that takes us to a vertex $u$ of $T_Y$. And here we repeat the argument: if $u$ is not in $S_Y$ the path ends here, otherwise we continue to a vertex in $T_X$. So we see that the endpoint $t$ of our path must be in $T_X-S_X$ or in $T_Y-S_Y$.

In the first case the last edge must have been an edge of $M_Y$ and we have an augmenting path for $M_X$. If we swap the edges on this path from $M_X$ to $M_Y$ and v.v. our 'new' $M_X$ still matches everything from $S_X$, and everything from $S_Y$ it matched before, but also $v$.

In the second case the last edge must have been an edge of $M_X$. If we swap edges on this path our 'new' $M_X$ still matches $S_X$, one vertex less in $T_Y-S_Y$, but one vertex more ($v$) in $S_Y-T_Y$.

Now simply perform this operation for all vertices $v$ of $S_Y-T_Y$ and we end up with a matching that matches all of $S_X$ and all of $S_Y$, as desired.

$\endgroup$
7
  • 1
    $\begingroup$ Hall's condition is satisfied, but the conclusion is just that there is an injective function from $f:S\to V(G)$ such that each vertex $v$ is adjacent to $f(v)$. Exactly how do you get a matching from that? Where do you use the fact that $G$ is bipartite? $\endgroup$ – bof Jan 15 '14 at 6:23
  • $\begingroup$ Hall's theorem does not immediately give the desired matching. It gives a matching of $S\cap V_1$ into $V_2$ and a matching of $S\cap V_2$ into $V_1$. The union of the two matchings covers $S$ but is not necessarily a matching. Its components are paths, cycles, and isolated vertices. The isolated vertices are in $V-S$ so we can ignore them. The cycles have even length so each cycle has a perfect matching. A path must have one endpoint in $S$ and the other in $V-S$, so it has a matching which covers all its vertices except possibly (depending on parity) the endpoint in $V-S$ $\endgroup$ – bof Jan 15 '14 at 6:47
  • $\begingroup$ You are right, bof, I was too optimistic. I'll remove this and think it over again. $\endgroup$ – Leen Droogendijk Jan 15 '14 at 12:43
  • $\begingroup$ It was harder to fix than I hoped :( $\endgroup$ – Leen Droogendijk Jan 15 '14 at 14:36
  • $\begingroup$ @LeenDroogendijk......could you kindly help me answering this question...math.stackexchange.com/questions/753395/… you $\endgroup$ – sayak Apr 14 '14 at 17:25
2
$\begingroup$

If the maximum degree is $k$, it is possible to keep adding edges and vertices until the graph is $k$-regular. Then by Hall's theorem $G$ will have a perfect matching. If you remove from the matching all the added edges and the isolated vertices you get a matching with the desired property.

$\endgroup$
6
  • $\begingroup$ Adding edges is not a right solution as is shown here: math.stackexchange.com/questions/165682/… $\endgroup$ – alop789312 Jan 17 '14 at 20:47
  • $\begingroup$ You are right, adding only edges does not do it. But, you can add vertices too and you still get the result. The idea is you can manage to make the graph a subgraph of $k$-regular graph $\endgroup$ – hbm Jan 17 '14 at 21:03
  • 1
    $\begingroup$ One way to do this in steps. At each steps, take two copies of $G$ and connect every vertex in one copy to its corresponding vertex in the second copy if the vertex has a degree less than the maximum degree. Note that the resulting graph is still simple and bipartite and the degrees of vertices smaller than the maximum degree are increased by one. $\endgroup$ – hbm Jan 18 '14 at 3:10
  • $\begingroup$ I dont see that it is still bipartite. $\endgroup$ – alop789312 Jan 18 '14 at 12:18
  • 2
    $\begingroup$ If $(X_1,Y_1,E_1)$ and $(X_2, Y_2, E_2)$ are the two copies. The set of new edges $E_3$ go between $X_1$ and $X_2$ and between $Y_1$ and $Y_2$ because they connect corresponding vertices that have degree smaller then the maximum. Your new graph is bipartite and is $(X_1 \cup Y_2, X_2 \cup Y_1, E_1 \cup E_2 \cup E_3)$. $\endgroup$ – hbm Jan 18 '14 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.