Skip to main content
Removed unnecessary and partly incorrect information.
Source Link

One can prove that a graph $G$ has a vertex cover of size $n - k$ if and only if the complement of $G$, let's call it $\overline{G}$, has a clique of size $k$, by choosing complementary vertex sets which then fulfill the requirements.

Now the complement of $L(K_n)$ is the well-known Kneser graph $K(n,2)$, by definition of Kneser graphs, and their clique number is $\lfloor \frac{n}{2} \rfloor$. Therefore, a minimal vertex cover of $L(K_n)$ would have size $\binom{n}{2} - \lfloor \frac{n}{2} \rfloor$, which is either $\frac{n^2}{2} - n$ or $\frac{n^2}{2} - n + 1$, depending on the parity of $n$.

One can prove that a graph $G$ has a vertex cover of size $n - k$ if and only if the complement of $G$, let's call it $\overline{G}$, has a clique of size $k$, by choosing complementary vertex sets which then fulfill the requirements.

Now the complement of $L(K_n)$ is the well-known Kneser graph $K(n,2)$, by definition of Kneser graphs, and their clique number is $\lfloor \frac{n}{2} \rfloor$. Therefore, a minimal vertex cover of $L(K_n)$ would have size $\binom{n}{2} - \lfloor \frac{n}{2} \rfloor$, which is either $\frac{n^2}{2} - n$ or $\frac{n^2}{2} - n + 1$, depending on the parity of $n$.

One can prove that a graph $G$ has a vertex cover of size $n - k$ if and only if the complement of $G$ has a clique of size $k$, by choosing complementary vertex sets which then fulfill the requirements.

Now the complement of $L(K_n)$ is the well-known Kneser graph $K(n,2)$, by definition of Kneser graphs, and their clique number is $\lfloor \frac{n}{2} \rfloor$. Therefore, a minimal vertex cover of $L(K_n)$ would have size $\binom{n}{2} - \lfloor \frac{n}{2} \rfloor$.

Source Link

One can prove that a graph $G$ has a vertex cover of size $n - k$ if and only if the complement of $G$, let's call it $\overline{G}$, has a clique of size $k$, by choosing complementary vertex sets which then fulfill the requirements.

Now the complement of $L(K_n)$ is the well-known Kneser graph $K(n,2)$, by definition of Kneser graphs, and their clique number is $\lfloor \frac{n}{2} \rfloor$. Therefore, a minimal vertex cover of $L(K_n)$ would have size $\binom{n}{2} - \lfloor \frac{n}{2} \rfloor$, which is either $\frac{n^2}{2} - n$ or $\frac{n^2}{2} - n + 1$, depending on the parity of $n$.