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.

  • $\begingroup$ @Gamow the two vertices you gave do not form an edge in $E$. $\endgroup$ Nov 14 '16 at 16:51
  • $\begingroup$ @AndrewMorgan In my final example $\deg(d)=4$ since it appears in both cycles. And the constraints are only for those edges with exactly one endpoint matched. So we don't consider $(u,v)$ if neither $u$ nor $v$ is matched. $\endgroup$ Nov 14 '16 at 17:10
  • $\begingroup$ Can you show an example where your property does not hold for a non-bipartite graph? $\endgroup$
    – JimN
    Nov 15 '16 at 19:20
  • 3
    $\begingroup$ @JimNastos a triangle should do the trick $\endgroup$
    – Yonatan N
    Nov 15 '16 at 22:52
  • $\begingroup$ You say in the question that $M$ is "... not necessarily maximal ..." ... so it can contain only one edge, doesn't it? What about a cycle of even length? $\endgroup$ Oct 2 '17 at 22:23

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$.

  • $\begingroup$ Yes, I wanted to use essentially the same argument to prove that practically any 3-regular bipartite expander can be made into a counterexample if we delete one vertex and connect its 3 neighbors to some other, sufficiently far vertices. $\endgroup$
    – domotorp
    Oct 4 '17 at 10:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.