views:

62

answers:

1

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!

+2  A: 

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.

Moron