1
$\begingroup$

Let $G$ be a bipartite graph with parts $A$ and $B$. Show that if $G$ has a matching that covers every vertex of $A$, then for every $A'\subseteq A$, we have $|N(A')|\geq|A'|$, where $N(A')$ denotes the set of neighbours of $A'$.

This sseems pretty obvious but I can't put it into correct words. If $G$ has a matching that covers every vertex of $A$ then the degree of all vertices of $A$ is going to be at least $1$ or else the matching wouldn't contain all vertices of $A$. So the number of neighbours of $A'$ is going to be at least the number of vertices of $A'$.

I don't know how to be rigorous with this. Also if anything that I have said is incorrect in any way, then please say.

Ok here is my new answer: Let $G=(V,E)$. Consider A'. Since we have a matching that covers all vertices of A, then this matching clearly covers all vertices of A'. The degree in each vertex of A' is going to be at least 1 - otherwise there cannot be a matching that covers all vertices in A'. Further, there cannot be any edge that share vertices in A' otherwise G would not be a bipartite graph. So for edge $uv \in E$, either u is in A' and v is in B or vise versa. This means edges that come from vertices in A' is going to be joined to vertices in B. Since we said the deg of each vertex in A' is at least 1, then there is clearly going to be at least |A'| edges that are incident to vertices in A'.

Since we have a matching that covers all vertices in A', and since each vertex degree is at least 1 in A', each vertex is going surely going to have at least $1$ neighbour that is different to the other neighbours that the other vertices in A' have. If it didn't then there would be an edge that shares the same vertex in A' meaning there would be no matching (that covers all vertices of A'). So this means there is at least going to |A'| neighbours in vertices of A' that are different to each other. This means $|N(A')|\geq |A'|$.

Now what do you think of it now? Again please point out ANYTHING that is wrong with it or can be improved or can be justified more.

$\endgroup$
  • $\begingroup$ A piece of meta advice I'd wish someone had given to me sooner, would be to never ever write down the word obvious anywhere near a proof. $\endgroup$ – Fasermaler Mar 13 '15 at 20:06
  • $\begingroup$ I never used that word anywhere in my answers... when I said 'obvious' that was not part of my answer. $\endgroup$ – snowman Mar 13 '15 at 20:07
  • $\begingroup$ Peace, I'm not judging or implying it was. It's just that a sure fire way of ticking off my professors would be to call anything obvious regarding proofs. I meant well to caution you about that. $\endgroup$ – Fasermaler Mar 13 '15 at 20:18
1
$\begingroup$

Hint:

  • The matching gives you a bijection between $A$ and some some subset of $N(A)$. In other words you can point out at least $|A|$ distinct vertices of $N(A)$.
  • Matching that covers $A$ covers also any $A'\subseteq A$.

Solution:

Let $M \subseteq E$ be the matching that covers $A$. It also covers $A'$, because $A' \subseteq A$. Let $M' \subseteq M$ be the set of edges of $M$ that are incident to the vertices of $A'$. In particular, $M'$ is also a matching that covers $A'$. No two edges of $M'$ share a vertex, hence vertices in $B' = V(M)\cap B$ are all distinct, so $|B'| = |M'| = |A'|$. Yet, all the vertices of $B'$ share an edge with some vertex of $A'$ (because of $M'$), hence $B' \subseteq N(A')$. Combining that with the previous equality we get $|N(A')| \geq |B'| = |A'|$.$$\tag*{$\square$}$$

I hope this helps $\ddot\smile$

$\endgroup$
  • $\begingroup$ So after that hint, can you just simply say the result we are trying to prove is true? Because I cant think of anything else to add to that... $\endgroup$ – snowman Mar 12 '15 at 23:42
  • $\begingroup$ @snowman That depends on how formal/informal you would like to be. If this would be an introductory course in graph theory or discrete math, then I would not accept it. $\endgroup$ – dtldarek Mar 13 '15 at 0:16
  • $\begingroup$ I would want to be as formal as I can. But I can't think of a way to use expressions to say what needs to be said. $\endgroup$ – snowman Mar 13 '15 at 0:18
  • $\begingroup$ @sandman Try again. For example, the attempt at proof in your post is wrong, because even if the degrees are $\geq 1$, then all these edges could connect to the same vertex. That is impossible if you have a matching, but you didn't used that. As you see "pretty obvious" does not make things automatically correct, try to write a proof with scrutiny that would catch this error in your initial reasoning. $\endgroup$ – dtldarek Mar 13 '15 at 8:35
  • 1
    $\begingroup$ @snowman That was a big improvement $\ddot\smile$ There are some minor things you could do better (e.g. you don't have to talk about degrees at all), but it's fine now. I would suggest to leave it as it is and go on with some new problem (you will learn more studying other problems rather than just dwelling on this one). For your convenience I've edited my answer to include a full solution. Please observe that mine is not perfect either, the goal is to be clear enough and don't miss out any of the important details (like the one with overcounting). Congratulations, well done! $\endgroup$ – dtldarek Mar 16 '15 at 11:52

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.