Statement: Minimum vertex cover number(𝜷) + Size of maximum Independent set(𝛼) = Size of vertex set (n)
Proof:
Statement 1:
A graph G(V,E) if S ⊆ V is a Vertex Cover then (V - S) is Independent Set.
Proof 1:
In the picture only green coloured edges are possible.
Now we can see that all the vertices in the set (V - S) can’t be adjacent. Hence (V - S) is an Independent Set. (Proved)
Statement 2:
A graph G(V,E) if S ⊆ V is a Independent Set then (V - S) is Vertex Cover.
Proof 2:
Again in the picture below only green coloured edges can be present and if red coloured edges are present then S can’t be an Independent Set because the vertices will be adjacent.
So where are all the adjacent edges ?
They must be in between S and (V - S) or in (V - S). So we can see (V - S) covers all the edges hence it is a Vertex Cover. (Proved)
Statement 3: 𝛼 + 𝜷 = n
Proof 3:
Size of any Verte Cover ≥ Size of minimum Vertex Cover(𝜷)
Size of any Independent Set ≤ Size of maximum Independent Set(𝛼)
From figure 1, 𝛼 ≥ |V - S| ⇒ 𝛼 ≥ n - 𝜷 ⇒ n ≤ 𝛼 + 𝜷 …………..(i)
From figure 2, 𝜷 ≤ |V - S| ⇒ 𝜷 ≤ n - 𝛼 ⇒ n ≥ 𝛼 + 𝜷 .....................(ii)
From (i) and (ii), n = 𝛼 + 𝜷 (Proved)
So here 𝛼 = 20 - 8 = 12
Credit: Deepak Poonia (Teacher of GO Classes)
