179 views
graph of 100 edges and 25 vertices..size of minimum vertex cover is 8..what is the size of  maximum independence set?

If C is a vertex cover of a graph, then Remaining vertices form an Independent Set.

Hence, Total number of Vertices = Minimum Vertex Cover + Size of Maximum Independent Set

=> This gives size of Maximum Independent Set = 25 - 8 = 17