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.

Given a bipartite graph G with two partition sets $U$ and $V$ of the same size $n$. In each set, there are d vertices of degree (n-d+1), and n-d vertices of degree (n-d). Can we find a perfect matching in this graph?

So basically, the two sets are the same in terms of degree sequence, although one has no idea how vertices are adjacent to each other. I tried to use Hall's theorem here, but i got stuck. Take any subset S of U that contain some vertices of degree n-d+1 and some of degree n-d, then I am not be able to show $|N(S)| \geq |S|$.

EDIT: The first question is solved and now a more general and perhaps research-oriented question is: What if in each set $U$ and $V$, there are $d$ vertices of degree AT LEAST $(n-d+1)$, and $n-d$ vertices of degree AT LEAST $(n-d)$. Can we still find a perfect matching?

The method for the previous question fails here.

share|improve this question
add comment

1 Answer 1

up vote 4 down vote accepted
+50

You can bound $\lvert N(S)\rvert$ from below by considering the worst case that all neighbours have the maximal degree, $n-d+1$. Then each vertex in $S$ of degree $n-d+1$ has as many outgoing edges as a worst-case neighbour has incoming edges, so the "cost balance" of such a vertex is neutral. Each vertex in $S$ of degree $n-d$ "saves" one edge, but there can be at most $n-d$ of these in $S$, so only $n-d$ edges can be "saved", whereas $n-d+1$ edges would have to be "saved" to "save" one worst-case neighbour. So no neighbour can be "saved" even in the worst case, and thus there must be as many neighbours as vertices in $S$.

I can write that out in formulas if you want, but you said you wanted a hint.

[Edit in response to request for formulas:]

Since all edges incident at a vertex in $S$ are also incident at a vertex of $N(S)$, we have

$$\sum_{w\in N(S)}\deg(w)\ge\sum_{v\in S}\deg(v)\;.$$

If $S$ contains $n_-$ vertices of degree $n-d$ and $n_+$ vertices of degree $n-d+1$, then

$$\begin{eqnarray} \sum_{v\in S}\deg(v)&=&n_-(n-d)+n_+(n-d+1)\\\ &=&(n_-+n_+)(n-d+1)-n_-\\\ &=&\lvert S \rvert (n-d+1)-n_-\\\ &\ge&\lvert S \rvert (n-d+1)-(n-d)\;, \end{eqnarray}$$

since there are only $n-d$ vertices of degree $n-d$. On the other hand, since no vertex has degree more than $n-d+1$, we also have

$$\sum_{w\in N(S)}\deg(w)\le \lvert N(S) \rvert (n-d+1)\;.$$

Putting this all together gives

$$\lvert N(S) \rvert (n-d+1) \ge \lvert S \rvert (n-d+1)-(n-d)\;,$$ $$\lvert N(S) \rvert \ge \lvert S \rvert -\frac{n-d}{n-d+1}\;.$$

But $\lvert N(S) \rvert$ and $\lvert S \rvert$ are integers and the last term is less than $1$, so we can drop the last term to conclude that $\lvert N(S) \rvert\ge\lvert S \rvert$. Linking this back to the original answer, each vertex in $S$ of degree $n-d$ can change the balance in the penultimate inequality by at most $1$, and there are at most $n-d$ such vertices, so the balance can only be changed by $n-d$, but it would have to change by $n-d+1$ to make a difference in the last inequality, where the division by $n-d+1$ corresponds to the fact that we need to "save" $n-d+1$ edges in order to "save" one worst-case neighbour.

share|improve this answer
    
Thank you, but I am quite slow in understanding your proof. Could you give out the formulas so I could understand it more clearly? –  Alex J. Mar 19 '11 at 0:01
    
@Taole Z: Done. –  joriki Mar 19 '11 at 8:21
    
Thanks. And I just added a follow-up question. It seems more complicated. –  Alex J. Apr 6 '11 at 5:46
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.