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.


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.