Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #8114

on bipartite graphs and matchings

Show all headers | View raw

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?

Back to comp.programming | Previous | Next | Find similar | Unroll thread

Thread

on bipartite graphs and matchings Daniel Bastos <dbastos@toledo.com> - 2017-10-21 18:15 -0200

csiph-web