Register

Graph

522 views
3 votes
3 votes
graph of 100 edges and 25 vertices..size of minimum vertex cover is 8..what is the size of  maximum independence set?
User Avatar

1 Answer

Best answer
4 votes
4 votes
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
• selected by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
Malusi asked Jan 12
105 views
Consider a weighted undirected graph with positive edge weights and let (u, v) be an [2] edge in the graph. It is known that the shortest path from source vertex r to u has weight 53 and shortest path from r to v has weight 65. Which statement is always true?
Consider a weighted undirected graph with positive edge weights and let (u, v) be an edge in the graph. It is known that the shortest path from source vertex r to u hasw...
User Avatar
0 votes
0 votes
1 answer
3
Dknights asked Dec 12, 2023
408 views
Regular and complete graph
which of the following statements is true: a complete graph is $(N-1)$ regular a $(N-1)$ regular is a complete graph
which of the following statements is true:a complete graph is $(N-1)$ regulara $(N-1)$ regular is a complete graph
User Avatar
1 votes
1 votes
1 answer
4
suryansh rajput asked Oct 2, 2023
194 views
Graph Theory
User Avatar
Link Copied!