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$.

  • $\begingroup$ I think you have the wrong number for $\tau$ here :) $\endgroup$ – Math1000 Feb 4 '16 at 8:12
  • $\begingroup$ 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? $\endgroup$ – ToiKri Feb 4 '16 at 8:15
  • $\begingroup$ I think you have the wrong definition of vertex cover. $\endgroup$ – 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. $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.