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 of the complete graph on $n$ vertices, what is the minimal cardinality that a vertex cover can have?
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$.
For Each $e \in E(K_n)$ write as $v_e$ the corresponding vertex in $V(L(K_n))$.
Let $M$ be any matching in $K_n$, and write as $L(M)$ the set of vertices $\{v_e \in V(L(K_n)); e \in M\}$. Then $V(L(K_n)) \setminus L(M)$ is a vertex-cover.
Now let $E'$ be any set of edges in $K_n$ where $E$ is not a matching, and write as $L(E')$ be the set of vertices $\{v_e \in V(L(K_n)); e \in E'\}$. Then
$V(L(K_n)) \setminus L(E')$ is NOT a vertex-cover.
As the maximum matching in $K_n$ has cardinality $\lfloor \frac{n}{2} \rfloor$ and $L(K_n)$ has $\frac{n(n-1)}{2}$ vertices, it follows that it suffices and is necessary for $C$ to have $\frac{n(n-1)}{2} - \lfloor \frac{n}{2} \rfloor$ vertices.
