Question

#2. Answer with explanations. Graph G with 12 vertices has 4 pair-wise nonadjacent vertices. What could be said about its minimum vertex cover of G? It has... Yes No Impossible to determine a) at least 4 vertices because Yes No Impossible to determine b) at most 8 vertices because

Answer 1

a. With 4 vertices we can not get the cover G. As ther are 4 pair wise non-adjacent vertices . We need atleast 4 vertices from there means , out of those 8 verices we need atleast 4 vertices and from left 4 vertice we need atleast 1 vertex to cover G.

b h g k a

So one of the possible Cover of G will {a,c,e,g,i}.

So, the answer will be No.

b.For a cover of a Graph , by defination the cover will be the set or sub set of all the vertex of a graph.

For by defination atmost we can take all the 12 vertices as the cover of G.