What is the relationship between minimum sized vertex covers and complete graphs?

Question

What is the relationship between the sizes of minimum sized vertex covers and complete graphs?

Answer 1

A set of vertices is a vertex cover iff its complement is an independent set.

Indeed, a set $S$ is a vertex cover if for all edges $(x,y)$, either $x \in S$ or $y \in S$.

Conversely, a set $S$ is an independent set if for all edges $(x,y)$, either $x \notin S$ or $y \notin S$.

Despite this strong relation between minimum vertex cover and maximum independent set, in some sense maximum independent set is much harder: while minimum vertex cover has several 2-approximation algorithms, it is NP-hard to approximate maximum independent set to within $n^{1-\epsilon}$.

Finally, let me mention that a set of vertices is an independent set in a graph iff it is a clique in the complement graph (formed by replacing edges by non-edges and vice versa). This gives a relation between minimum vertex cover and maximum clique on the complement graph.

Answer 2

The size of minimum vertex cover in a complete graph $K_n$ (on $n$ vertices for $n > 1$) is equal to $n-1$.

It is easier to understand using the fact that minimum vertex covers correspond to the complements of maximum independent vertex sets. In a complete graph $K_n$ the maximum independent set is clearly has only one vertex and so the size of a minimum vertex cover is equal to $|V| - \text{ size of maximum independent vertex set} = n-1$.