Minimum vs Minimal vertex covers
I am studying for an exam and one of the sample questions is as follows:
Vertex cover: a vertex cover in a graph is a set of vertices such that each edge has at least one of its two end points in this set.
Minimum vertex cover: a MINIMUM vertex cover in a graph is a vertex cover that has the smallest number of vertices among all possible vertex covers.
Minimal vertex cover a MINIMAL vertex cover in a graph is a vertex cover that does not contain another vertex cover (deleting any vertex from the set would create a set of vertices that is not a vertex cover)
Question: A minimal vertex cover isn't always a minimum vertex cover. Demonstrate this with a simple example.
Can anyone get their head around this? I am failing to see the distinction between the two. More importantly, I'm having a hard time visualizing it.
I seriously hope he's not gonna ask odd questions like this one on the exam!
Answer
Consider the following undirected graph:
The set of vertices {2,4,5} is a minimum vertex cover of the graph. Why? because it's a vertex cover (all edges are covered) and there is no other vertex cover with fewer vertices.
The set of vertices {2,3,5,6,7} is a minimal vertex cover. Why? because it's a vertex cover and any non-trivial subset of {2,3,5,6,7} is not a vertex cover. Try removing any vertex from {2,3,5,6,7} and see that you leave an uncovered edge. What makes a vertex cover minimal is an inability to reduce it. You cannot make the set smaller than it already is and still get a vertex cover (without inserting vertices to it).
Obviously, the given minimal vertex cover isn't a minimum vertex cover because a minimum vertex cover has three vertices and our minimal vertex cover has 5 vertices. Hence, not every minimal vertex cover is also a minimum vertex cover.
Every minimum vertex cover is also a minimal vertex cover because removing vertices from a minimum vertex cover will result in a set of vertices of a size smaller the the minimum cover. Thus, any non-trivial subset of a minimum vertex cover is not a vertex cover, and therefore a minimum vertex cover is also minimal.