8
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ @Gamow the two vertices you gave do not form an edge in $E$. $\endgroup$
    – Wei Zhan
    Nov 14, 2016 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$
    – Wei Zhan
    Nov 14, 2016 at 17:10
  • $\begingroup$ Can you show an example where your property does not hold for a non-bipartite graph? $\endgroup$
    – JimN
    Nov 15, 2016 at 19:20
  • 3
    $\begingroup$ @JimNastos a triangle should do the trick $\endgroup$
    – Yonatan N
    Nov 15, 2016 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, 2017 at 22:23

1 Answer 1

4
+100
$\begingroup$

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

$\endgroup$
1
  • $\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, 2017 at 10:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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