Proving minimum vertex cover

Question

Every vertex cover of a graph contains a minimum vertex cover.

I know the statement to be true but how do I go proving it?

Answer 1

Let $C = \{v_{1}, ..., v_{k} \}$ be a vertex cover. By definition of a vertex cover, every edge is incident to some vertex in $C$. Suppose $C$ contains no minimum vertex cover. So begin removing vertices inductively. Since there is no minimum vertex cover, we can keep removing vertices from $C$ in this manner. The process will terminate since $C$ is finite. This implies $\emptyset$ covers $G$. If $G = \emptyset$, then $\emptyset$ covers $G$ and is a minimal cover, a contradiction.

If $\emptyset$ does not cover $G$, then that means we removed too many vertices. Hence, we need a minimum number of vertices to cover $G$. So we get another contradiction.