Not able to understand this graph property.

88 Views Asked by At

I read that in a simple graph, |minimal vertex cover| $\leq 2$|maximal matching|.

Consider a graph show below. Here a minimal vertex cover can be $\{B,C,D,E\}$ which has a size of 4 and size of maximal matching is just 1. So, $4>2*1$ and the property doesn't seem to satisfy.

Can someone help me with this?

enter image description here

1

There are 1 best solutions below

3
On BEST ANSWER

The statement is that the $|\text{Smallest Vertex Cover}|\leq 2|\text{Maximal Matching}|$, not minimal.

If you have a maximal Matching $M$ and you choose the vertices of the edges of $M$ you have a vertex cover of $2|M|$ vertices. This covers every edge because a not covered edge could be added to $M$, which cannot be because $M$ is maximal.

If we have one Vertex cover with size $2|M|$, the smallest must be smaller or equal in size. As your example shows one cannot replace smallest with minimal.