Bipartite matching with degree domination

Question

Given an unweighted bipartite graph $G=(V, E)$. Is it true that there always exists a nonempty matching $M\subseteq E$ (not necessarily maximal), such that for every $(i,j)\in E$ with $i$ matched and $j$ unmatched, it holds $\deg(i)>\deg(j)$? Here $(i,j)$ is not ordered, i.e., $i$ can be on either side.

My intuition on why this is true is, when every vertex in $V$ has the same degree, there is always a perfect matching which is the matching we required. For some simple graph structures like trees or unicyclic graphs a maximal matching is desired since the degree of a leaf is always smaller than its parent.

I tried to prove it from Hall's theorem but failed. Part of the complexity of this problem is that the solution is not always a maximal matching. For instance, considering a graph consisting of two 4-cycles $abcd$ and $defg$. Then $M=\{ab,cd\}$ and its symmetrical matchings are the only solutions, which are not maximal.

Answer 1

There does not always exist a matching with your property in a bipartite graph.

Consider for example the graph $G = (V, E)$ where

• $V = \{a_1, a_2, a_3, b_1, b_2, b_3, c_1, c_2, d_1, d_2, x\}$ and
• $E = \{a_1, a_2\} \times \{c_1, c_2, x\} \cup \{b_1, b_2\} \times \{d_1, d_2, x\} \cup \{(a_3, c_1), (a_3, d_2), (a_3, x), (b_3, d_1), (b_3, c_2), (b_3, x)\}$

This graph is bipartite (with $V_1 = \{a_1, a_2, a_3, b_1, b_2, b_3\}$ as one part and $V_2 = \{c_1, c_2, d_1, d_2, x\}$ as the other). Every vertex in this graph except $x$ has degree $3$. Vertex $x$ has degree $6$.

Suppose, for the sake of contradiction, that a matching $M$ with your property exists. Consider any two adjacent vertices $v_1$ and $v_2$ that have the same degree. It turns out that the conditions on $M$ imply that both of these vertices have the same matched-or-not status (i.e. either both or neither of the vertices must be matched in $M$). This can be proved very simply by contradiction: suppose one vertex (wlog $v_1$) is matched and the other is not; then since there is an edge between them, the given property on $M$ tells us that $deg(v_1) > deg(v_2)$, which is a contradiction.

Thus, the matched-or-not status of adjacent vertices of the same degree is the same. Then if a set of vertices has the property that every vertex has the same degree and the subgraph induced by these vertices is connected, we can apply this rule multiple times to conclude that all vertices in the set must have the same matched-or-not status. In particular, in $G$ the matched-or-not status of every vertex in $V \setminus \{x\}$ must be the same since these vertices all have degree-$3$ and are connected. In other words, either every vertex in $V \setminus\{x\}$ is matched in $M$, or no such vertex is matched in $M$. If the matched-or-not status for these vertices is "matched" then every vertex in the $V_1$ part of the bipartition is matched in $M$; this is impossible since there are more vertices in $V_1$ than in the other part $V_2$. If the matched-or-not status for these vertices is "not matched" then the only vertex in $G$ that can be matched in $M$ is $x$; since a non-empty matching (as $M$ must be) matches at least two vertices, we see that this case is also impossible.

By contradiction, a matching $M$ with the property in question does not exist in $G$.