The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+3 votes
graph of 100 edges and 25 vertices..size of minimum vertex cover is 8..what is the size of  maximum independence set?
asked in Graph Theory by Veteran (21.5k points) | 179 views

1 Answer

+4 votes
Best answer
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
answered by Veteran (51.6k points)
selected by

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,234 questions
40,919 answers
39,834 users