The vertex covering of a graph that has isolated vertices

Question

I know the theorem that in a graph G=(V,E) which has no isolated vertex, a set $C\subset V$ is a vertex covering in G if and only if the set V‐C is an independent set in G. I want to know whether this theorem will hold if G has isolated vertices? Why? Thanks in advance!

Answer 1

Sure, why not. The reasoning behind that statement doesn't depend on whether or not there are isolated vertices.

Let $C \subseteq V$ be an arbitrary set of vertices. $C$ is a vertex cover if and only if each edge of the graph has at least one end in $C$. This is the same as saying that there are no edges in the graph whose both ends are in $V \setminus C$. This is the same as saying that no two vertices in $V \setminus C$ are connected by an edge. That is synonymous to saying that $V\setminus C$ is an independent set.

UPDATE: You can find the short version of this argument on wikipedia.

If this isn't convincing, you can think about isolated vertices specifically. If $C$ is a vertex cover and $v$ is an isolated vertex, then you can see from the definition that both $C \cup \{v\}$ and $C \setminus \{v\}$ are also vertex covers. In the same vein, if $D$ is an independent set and $v$ is an isolated vertex, then $D \cup \{v\}$ and $D \setminus \{v\}$ are also independent sets. What this tells us is that isolated vertices have no say in deciding which sets are vertex covers and which are independent sets. So they cannot spoil your theorem.