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

Solution 1 and 2: In the given example, there is no information that is provided regarding the edges present inside the graph. The vertex cover of an undirected graph is nothing but the subset of all of its vertices such that for each and every edge in the graph (u,v) either u or v is present in the subset (vertex cover). The main aim of this algorithm is to cover all the edges within the graph. Now,since there is no information regarding the edges present in the graph, no decision can be made regarding the vertices present in the vertex cover of this graph. Therefore, the correct option is Imposssible to determine.

Here's the solution to your question, please provide it a 100% rating. Thanks for asking and happy learning!!