From the graph given below, which of the following statement is n
From the graph given below, which of the following statement is not true?
NOTE:
β2 denotes maximum independent set.
α2 denotes minimum vertex cover.
A. The set {b, f} is a maximum independent set.
B. β<sub style="">2</sub> = 2
C. α<sub style="">2 </sub>= 5
D. {a, b, c, e , g} is a minimum vertex cover.
Please scroll down to see the correct answer and solution guide.
Right Answer is: D
SOLUTION
Concept:
A subset of vertices is called an independent vertex set if no two vertices are adjacent. An independent vertex set is maximal independent set if no other vertex can added to it.
Maximum independent set if the maximal independent set with maximum number of vertices. It is denoted by .
Explanation:
1. The set {b, f} is a maximum independent set.
This statement is correct. The independent vertex set of 3 vertices is not possible because there is cycles of length 3. So, this is the maximum independent set.
2. β2 = 2
This is also correct. From 1st statement, it is true.
3. α2 = 5
There is a condition in the graph, i.e. α2 + β2 = number of vertices
So, 2 + α2 = 7, α2 = 5
Given statement is correct.
4. {a, b, c, e , g} is a minimum vertex cover.
These vertices cannot cover all the edges. So, it is not the minimum vertex cover.