For $n\in\mathbb{N}$ we consider the set $\{1,\ldots,n\}$ and define the *line graph $L(K\_n)$ of the complete graph $K\_n$* as follows:


* $V(L(K\_n)) = \big\{\{a,b\}: a,b\in \{1,\ldots, n\}, a\neq b \big\}$;
* $E(L(K\_n)) = \big\{\{x,y\}: x,y\in V(L(K\_n)) \text{ and } x\cap y \neq \emptyset\big\}$.


For any graph $G=(V,E)$ the *Hadwiger number* $\eta(G)$ is the largest $n\in \omega$ such that $K\_n$ is a minor of $G$.


In [this post](https://mathoverflow.net/questions/202776/implication-between-erd%C3%B6s-faber-lovasz-conjecture-and-hadwigers-conjecture/202778#202778) it is shown that $\eta(L(K\_5)) \geq 6$, and it's easy to see that $\eta(L(K\_n)) \geq n+1$ for $n\geq 5$.


**Question**: Given a positive integer $k\in\mathbb{N}$, is there $n\in \mathbb{N}$ such that $\eta(L(K\_n)) \geq k\cdot n$?



The Hadwiger number of $L(K_n)$
**Claim.** For all even $n \geq 4$, $\eta(L(K\_n)) \geq \frac{3n-4}{2}$ and for all odd $n \geq 3, \eta(L(K\_n)) \geq \frac{3n-3}{2}$ 


*Proof.*
A clique-minor of size $k$ in $L(K\_n)$ corresponds to $k$ edge-disjoint connected subgraphs of $K\_n$ which pairwise intersect. 


Let $n$ be even. For our $\frac{3n-4}{2}$ subgraphs we first take the $n-1$ edges of a star centered at $x$. By an old theorem of Walecki, the edges of $K\_n-x$ can be decomposed into Hamiltonian cycles. There are $\frac{1}{2}(n-2)$ such cycles, giving us $\frac{3n-4}{2}$, as required. 


For $n$ odd, we use the same argument but take a Hamiltonian path decomposition of $K\_n-x$ instead. 


