What is the relationship between minimum sized vertex covers and complete graphs? What is the relationship between the sizes of 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$.