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.
Best Answer
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.