I know that I can find the minimum vertex cover of a bipartite graph by first finding the maximum matching and then using Konig's Theorem to turn this matching into a vertex cover of the same order.
The result obtained is only one of what could be many valid vertex covers. In the following graph, {A,B}, {C,D}, and {B,C} are all valid covers. Applying the Konig method yields the cover {A,B}.*
(A)=====(C)
/
/
/
(B)=====(D)
How would you check for the existence of a minimum vertex cover that includes a given important vertex, say, vertex D?
My first guess is to flip the graph and find another minimum vertex cover. In the above case, this would yield {C,D}. If neither solution contains the important vertex, it's not part of any minimum cover. However, I haven't been able to prove this to myself.
*A little elaboration: edge AC and BD form the matching. In the algorithm described above, you start by treating the graph asymmetrically, labeling the sides L (left) and R (right). Initially, all L and none of the R vertices are part of the vertex cover. Now build a new set T of vertices by traversing according to the following rule: Start at the exposed vertices (not part of any matching) on the left side, travel right along all unmatched edges, then travel left along all matched edges, continuing back and forth until path termination. All visited vertices are added to set T. Set T is subtracted from L and added to R to produce the vertex cover solution. In the example graph, there is NO traversal, since there are no exposed vertices on the left side.
