Hi!
I'm working on problem 16.1.15 here:
http://books.google.com/books?id=HuDFMwZOwcsC&pg=PA424&lpg=PA424&dq="every+bipartite+graph+has+an+essential+vertex"&source=bl&ots=xIlcxGVWD1&sig=Vuw5v9EglesXu0bc2RxH_tk-omM&hl=en&sa=X&ei=T9hTT4CmN8e10AGh8rnjDQ&ved=0CDQQ6AEwAg#v=onepage&q="every bipartite graph has an essential vertex"&f=false
and am struggling with part (b).
I have been following the hints provided here:
16.1.15 (b) Let G[X, Y ] be a bipartite graph and let xy be an edge of G with
x ∈ X and y ∈ Y . Suppose that neither x nor y is essential. Then there exist
maximum matchings Mx and My of G such that Mx covers x but not y, and My
covers y but not x. Show that no component of G[Mx△My] contains both x and y.
Let Px and Py be the components of G[Mx△My] containing x and y, respectively.
Obtain a contradiction by considering the subgraph (Px ∪ Py) + xy. (Thus, in a
bipartite graph, at least one end of each edge is essential.)
And I'm good up to the part at the end where we're looking at (Px ∪ Py) + xy and trying to find a contradiction. I'd really appreciate any guidance on whats going wrong here.
Thanks!
I'm working on problem 16.1.15 here:
http://books.google.com/books?id=HuDFMwZOwcsC&pg=PA424&lpg=PA424&dq="every+bipartite+graph+has+an+essential+vertex"&source=bl&ots=xIlcxGVWD1&sig=Vuw5v9EglesXu0bc2RxH_tk-omM&hl=en&sa=X&ei=T9hTT4CmN8e10AGh8rnjDQ&ved=0CDQQ6AEwAg#v=onepage&q="every bipartite graph has an essential vertex"&f=false
and am struggling with part (b).
I have been following the hints provided here:
16.1.15 (b) Let G[X, Y ] be a bipartite graph and let xy be an edge of G with
x ∈ X and y ∈ Y . Suppose that neither x nor y is essential. Then there exist
maximum matchings Mx and My of G such that Mx covers x but not y, and My
covers y but not x. Show that no component of G[Mx△My] contains both x and y.
Let Px and Py be the components of G[Mx△My] containing x and y, respectively.
Obtain a contradiction by considering the subgraph (Px ∪ Py) + xy. (Thus, in a
bipartite graph, at least one end of each edge is essential.)
And I'm good up to the part at the end where we're looking at (Px ∪ Py) + xy and trying to find a contradiction. I'd really appreciate any guidance on whats going wrong here.
Thanks!