If this link can be any help


A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set.

A minimum vertex cover is a vertex cover with minimal cardinality.

Consider a set of all minimum vertex covers of a given bipartite graph.

our task is to divide all the vertices of the graph into three sets.

A vertex is in set N (“Never”) if there is no minimum vertex cover containing this vertex.

A vertex is in set A (“Always”) if it is a part of every minimum vertex cover of the given graph.

If a vertex belongs neither to N nor to A, it goes to the set E (“Exists”).

How to classify vertices?

I don't understand the variables. I have an edge from maximum matching then I might have both the endpoints of that edge in the vertex cover. But this scheme does not allow this.


  • $\begingroup$ Did you ask this question twice? cs.stackexchange.com/questions/107164/… $\endgroup$
    – lox
    Commented Apr 21, 2019 at 15:52
  • 1
    $\begingroup$ Please do not copy parts from other questions, that does not help much. If your question is different from the question linked, please explain the problem clearly. In particular, I'm not able to access the link you provided at the moment, so you should mention the relevant parts here. $\endgroup$
    – Discrete lizard
    Commented Apr 21, 2019 at 16:51