What is the relationship between minimum sized vertex covers and complete graphs?
The size of minimum vertex cover in a complete graph $K_n$ (on $n$ vertices for $n &gt; 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$.