Path: csiph.com!aioe.org!.POSTED!not-for-mail From: Daniel Bastos Newsgroups: comp.programming Subject: on bipartite graphs and matchings Date: Sat, 21 Oct 2017 18:15:39 -0200 Organization: Aioe.org NNTP Server Lines: 28 Message-ID: <86a80kdzpw.fsf@toledo.com> NNTP-Posting-Host: wHY0fnegm+Nybzjaa5/zbQ.user.gioia.aioe.org Mime-Version: 1.0 Content-Type: text/plain X-Complaints-To: abuse@aioe.org User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (windows-nt) X-Notice: Filtered by postfilter v. 0.8.2 Cancel-Lock: sha1:swpLhrsOix1b4J2js1Wj4pwh/00= Xref: csiph.com comp.programming:8114 I've a question about the proof of the converse of Theorem 5.2 in ``Graph Theory with Applications'' by J.A. Bondy and U.S.R. Murty, 1976, North-Holland. --8<---------------cut here---------------start------------->8--- Theorem. Let G be a bipartite graph with bipartition (X,Y). Then G contains a matching that saturates every vertex in X if and only if |N(S)| >= |S| for all S subset X. (5.2) Proof. Suppose that G contains a matching M which saturates every vertex in X, and let S be a subset of X. Since the vertices in S are matched under M with distinct vertices in N(S), we clearly have |N(S)| >= |S|. Conversely, suppose that G is a bipartite graph satisfying (5.2), but that G contains no matching saturating all the vertices in X. We shall obtain a contradiction. Let M* be a maximum matching in G. By our supposition, M* does not saturate all vertices in X. Let u be an M*-unsaturated vertex in X, and let Z denote the set of all vertices connected to u by M*-alternating paths. Since M* is a maximum matching, it follows from theorem 5.1 that u is the only M*-unsaturated vertex in Z. [...] --8<---------------cut here---------------end--------------->8--- Comment. Whoa! How come u is in Z? Z is the set of all vertices connected to u. But u is not connected to itself because G is bipartite. So there's no way u could be in Z. What's going on there?