Minimum vs Minimal vertex covers
- by panicked
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!