6 5 4 2 1 3 Vertex Cover: For the graph above, select all the correct statements

Question

6 5 4 2 1 3 Vertex Cover: For the graph above, select all the correct statements below (note that incorrect choices are penalized): Select one or more: A. A minimum vertex cover size in this graph is 5. B. Nodes (2,3,4,5,6) form a vertex cover in this graph. C. If I used a greedy heuristic to find a vertx cover, I would start with node 3 in this graph. D. Unlike VC search, my greedy heuristic for the IS would start with the node with the fewest number of adjacent nodes (smallest degree). E. If VC is a vertex cover in graph G, then in its complement graph, these nodes from VC form a clique. FAll of the above. G. Every graph has only ONE minimum vertex cover set. H. If G-(n, m), then the size of the VC must be upper bounded by m/2. I. If the graph has 3-clique, then the VC includes only one node from this clique.

Explanation / Answer

----------------------------------------------------------------------------------------------

A. True
B. False
C.True
D.True
E. False
F. False
G. False
H True
I.True

Related Questions

Navigate

• Browse (All)
• Browse 6
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.