Discussion
Let G(V, E) be a simple, undirected graph. A vertex cover of G is a subset \(V' \subseteq V\) such that for every \((u, v) \in E\), \(u \in V'\) or \(v \in V'\). Let the size of the smallest vertex cover in G be k. Let S be any vertex cover of size k.
For a vertex \(v \in V\), which of the following constraints will always ensure that \(v \in S\) ?
Answer: A
The constraint that always forces v into S is The degree of v is at least k + 1.
If v were not in S, every edge at v would have to be covered by its other endpoint, so all of v's at least k + 1 neighbours would be in S. That makes S larger than k, a contradiction. So v must be in every minimum vertex cover.
The other conditions do not force it. In the path a-b-c the minimum cover is {b}, so k = 1, and a lies on a path of length 2 = k + 1 without being in the cover. In a triangle k = 2, every vertex lies on a cycle of length 3 = k + 1 and in a clique of size 2 = k, yet any one vertex can be left out of a minimum cover.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development