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

Groups > comp.programming > #8113

on symmetric difference between matchings

Show key headers only | View raw

I'd appreciate an explanation of the proof of the converse of Theorem
5.1 in ``Graph Theory with Applications'' by J.A. Bondy and
U.S.R. Murty, 1976, North-Holland.

--8<---------------cut here---------------start------------->8---
Theorem 5.1.  A matching M in G is maximum <--> G contains no
M-augmenting path.

Proof. [...]  Conversely, suppose that M is not a maximum matching, and
let M' be a maximum matching in G.  Then 

  |M'| > |M|      (5.1)

Set H = G[M Delta M'], where M Delta M' denotes the symmetric difference
of M and M' (see figure 5.2).
--8<---------------cut here---------------end--------------->8---

Comment.  My understanding of symmetric difference of two sets is that
it's the union of both sets without their interesection.  Figure 5.2
seems to confirm that.

--8<---------------cut here---------------start------------->8---
Each vertex of H has degree either one or two in H, since it can be
incident with at most one edge of M nad one edge of M'.
--8<---------------cut here---------------end--------------->8---

Comment.  I can see that.  H is the symmetric difference of two
matchings.  By themselves, each matching offers only vertices of degree
1.  Taking their union, vertices might coincide and some degree might
increase, but after we take out their intersection, we're sure of
increasing each degree at most by 1, hence 2 at most.  

From this point on, I can't see anything.  In figure 5.2, I guess we
have two components there, both which are paths.  (Maybe I should
construct a graph with two matchings whose symmetric difference gives me
a cycle, then I might see that it must be even.)

--8<---------------cut here---------------start------------->8---
Thus each component of H either an even cycle with edges alternately in
M and M', or else a path with edges alternately in M and M'.  By (5.1),
H contains more edges of M' than of M, and therefore some path component
P of H must start and end with edges of M'.  The origin and terminus of
P, being M'-saturated in H, are M-unsaturated in G.  Thus P is an
M-augmenting path in G.
--8<---------------cut here---------------end--------------->8---

Comment.  We had assumed G contained no M-augmenting path.

Thank you!

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

Thread

on symmetric difference between matchings Daniel Bastos <dbastos@toledo.com> - 2017-10-21 17:57 -0200

csiph-web