Minimum vs Minimal vertex covers

Question

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!

Bullard

Answer 1

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.

Embosom

Answer 2

Consider the graph

A --- B --- C

B is the minimum vertex cover.

A,C is a minimal vertex cover. Remove either A or C, you are not left with a vertex cover.

Thursby