I wanted to clarify if this is possible, so I thought about a possible vertex cover that can also serve as an independent set:

Independent Set/Vertex Cover
So, to clarify, am I right to say that the nodes in red are both (i) a vertex cover, and (ii) an independent set?

Edit: I was confused by the theorem that states "If G = (V,E) is a graph, then S is an independent set <-> V-S is a vertex cover." So I thought that a vertex cover and an independent set are mutually exclusive.


1 Answer 1


If something satisfies the definition of $X$ and the definition of $Y$, then it is both an $X$ and a $Y$.

Although it's true that, whenever $S$ is independent, $V\setminus S$ is a vertex cover, it's possible for both $S$ and $V\setminus S$ to be independent: this happens when $S$ is one side of a bipartite graph, as is the case in the example in the question.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.