# Size of minimum vertex cover on complete graph

I know that the maximum size of an independent vertex set, also known as the independence number and denoted by $\alpha$, plus the the size of the minimum vertex cover, $\tau$, is equal to the number of vertices in the graph, $n$.

$$\alpha(G) + \tau(G) = |G|$$

However, for a complete graph I don't understand how this is true. Take $K_4$, it seems to have $\alpha = \tau = 1$ but in this case $n = 4$.

• I think you have the wrong number for $\tau$ here :) – Math1000 Feb 4 '16 at 8:12
• Seems like it! I was under the impression $\tau$ was the smallest number for which I could choose a vertex set that was connected to all the other vertices? How come this is 3 in $K_4$ and not 1? – ToiKri Feb 4 '16 at 8:15
• I think you have the wrong definition of vertex cover. – Math1000 Feb 4 '16 at 8:16

Given the complete graph $K_n$, it is clear that $\alpha(K_n)=1$ as any two vertices are adjacent and thus any set with more than one vertex is not independent. Similarly, any subset of less than $n-1$ vertices cannot be a vertex cover, as it would not include an edge in the graph, so $\tau(K_n)=n-1$. So the formula is valid: $$\alpha(K_n) + \tau(K_n) = 1 + (n-1) = n.$$