edited by
426 views
0 votes
0 votes

Which of the following is true?

  1. The size of the maximum independent set on G is the same as the size of maximum clique on G'(Complement of G)
  2. The size of minimum vertex cover on G is the same as the size of maximum clique on G'(complement of G)
  3. The size of minimum vertex cover on G is the same as the size of maximum clique on G' 
edited by

1 Answer

0 votes
0 votes
A is true for any simple graph G because an independent set in simple graph G becomes clique in complement of G and vice versa.

Option B is false. For example, take an edgeless graph on 4 vertices, so size of minimum vertex cover is 0 but size of maximum clique in complement of G is 4.

Statement B and C are same.

Related questions

2 votes
2 votes
1 answer
2