I'm trying to show that every nonempty bipartite graph has an essential vertex. (A vertex is essential if it is covered by every maximum matching).
I've been following these hints:
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.)
I'm good with everything until we're considering (Px ∪ Py) + xy. I don't really see where the contradiction is. I think I'm having trouble picturing what is going on. any guidance would really be appreciated!
I've been following these hints:
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.)
I'm good with everything until we're considering (Px ∪ Py) + xy. I don't really see where the contradiction is. I think I'm having trouble picturing what is going on. any guidance would really be appreciated!