If $G=(V,E)$ is a simple, undirected graph, we say $C\subseteq V$ is a *vertex cover* if for any $e\in E$ we have $e\cap C \neq \emptyset$.


Let $n>1$ be an integer. If $L(K\_n)$ denotes the [line graph](https://en.wikipedia.org/wiki/Line_graph) of the complete graph on $n$ vertices, what is the minimal cardinality that a vertex cover can have?



Vertex-covering number of $L(K_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](http://mathworld.wolfram.com/KneserGraph.html "Kneser graph definition"), 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$.


