can a vertex be both part of independent set and minimum vertex cover

469 Views Asked by At

Given an edge in a graph G, both ends cannot be part of independent set and both ends(vertices of edge) can not be part of minimum vertex cover set.

But can 1 end vertex be both independent set and also in minimum vertex cover.

In my textbook there is a theorem that if S is minimum vertex cover then its complement is independent set. I understood the proof. But i am not able to get clue why a single vertex be part of both independent set and minimum vertex cover.

1

There are 1 best solutions below

5
On

Sure it can: Let $G$ be any complete bipartite graph with the same number of vertices on each side. Then either side is both a minimum vertex cover and a [maximum-sized] independent set.

Actually, even if $G$ has more vertices on one side than another, the side with the most vertices is both a minimum vertex cover and a [maximum-sized] independent set.