Perfect matching for a particular type of bipartite graphs

Question

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

Answer 1

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.

Answer 2

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.