GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 2

Question

The size of the minimum vertex cover of the below graph is _________

Answer 1

The vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.

A minimum vertex cover is a vertex cover having the smallest possible number of vertices for a given graph. The size of a minimum vertex cover of a graph G is known as the vertex cover number and is denoted $\tau(G).$

Every minimum vertex cover is a minimal vertex cover (i.e., a vertex cover that is not a proper subset of any other cover), but not necessarily vice versa.

Minimum vertex covers correspond to the complements of maximum independent vertex sets.

For the given graph, size of minimum vertex cover $=5,$ shown in cyan color below.


So, the correct answer is $5$.

Comments

https://stackoverflow.com/questions/3042609/minimum-vs-minimal-vertex-covers

For minimal vertex cover.