Perfect matching for a particular type of bipartite graphs Let $G = (V_1 \cup V_2, E)$ be a connected and bipartite graph such that:
(1) The number of vertices of $V_1$ is equal to the number of vertices of $V_2$, i.e., $|V_1| = |V_2| = N$ for some $N \in \mathbb{N}$.
(2) For every vertex $v \in V_1$, the degree of $v$ satisfies $2 \leq \mathrm{deg}(v) \leq N$; the same holds for every vertex in $V_2$.
(3) For $2 \leq i \leq N$, the number of vertices of degree $i$ in $V_1$ is equal to the number of vertices of degree $i$ in $V_2$, i.e., for every $2 \leq i \leq N$,
\begin{equation}
\big| \{v \in V_1 \,|\, \mathrm{deg}(v) = i\} \big| = \big| \{v \in V_2 \,|\, \mathrm{deg}(v) = i\} \big|.
\end{equation}
The question is: For any graph $G$ that satisfies these conditions, does there always exist a perfect matching between $V_1$ and $V_2$?
Clearly, if all vertices have the same degree, then the claim follows from Hall's theorem. The point here is that rather than assuming all vertices have the same degree, I assume that the number of vertices having a particular degree and belonging to either $V_1$ or $V_2$ are the same. The claim under the current setting is not true if we allow degree-$1$ vertices, and this can be verified by simple counter-examples. However, when all degrees are larger than $1$ and when the above (1) and (3) hold, I have not found a counter-example where no perfect matching exists.
Anyone has an idea? Thanks very much
 A: Here's a graph satisfying your conditions that does not have a perfect matching:
$V=\{1,\ldots,7,1',\ldots,7'\}$
$E=\{11',14',15',16',17',24',25',36',37',1'4,1'5,1'6,1'7,2'4,2'5,3'6,3'7\}$
If I understood your conditions correctly, and if I wrote the graph down correctly, then it should be an answer. To check:
There is one vertex of degree 5 on each side (1 and 1'). There are six vertices of degree 2 on each side (all others).
Now wlog you match vertex 1 not with 4' or 5' (else swap the labels {6',7'} with {4',5'}). You must match 4' with 2, and you must match 5' with 2, but this is a contradiction.
A: In general, we can ask for any minimum degree (not just $2$), and for the degree sequences on both sides to be equal, and still have no perfect matching.
For any $k$, pick $N > 2k$. For $i=1,2$, partition $V_i$ into $A_i \cup B_i$ with $|A_i| = k$ and $|B_i| = N-k$. Define adjacencies as follows:


*

*All vertices of $A_1$ are adjacent to all of $V_2$.

*All vertices of $A_2$ are adjacent to all of $V_1$.

*There are no other edges.


Here is an example with $k=3$ and $N=10$:

In this graph, all degrees are at least $k$, and the degree sequences in $V_1$ and $V_2$ are equal: both degree sequences are $$\underbrace{N, N, \dots, N}_k, \underbrace{k, k, \dots, k}_{N-k}.$$
However, $A_1 \cup A_2$ is a vertex cover of order $2k$, so by Kőnig's theorem, there is no matching larger than $2k$. In particular, there is no matching of size $N$: no perfect matching.
