Let $\mathcal{ F}$ be a family of graphs. The Tur\'{ a}n number $ex(n;\mathcal{ F})$ is defined to be the maximum number of edges in a graph of order $n$ that is $\mathcal{ F}$-free. In 1959, Erd\H{ o}s and Gallai determined the Tur\'an number of $M_{ k+1}$ (a matching of size $k+1$) as follows: \[ ex(n;M_{ k+1})= \max\left\{ \binom{ 2k+1}{ 2},\binom{ n}{ 2}-\binom{ n-k}{ 2}\right\}. \] Since then, there has been a lot of research on Tur\'an number of linear forests. A linear forest is a graph whose connected components are all paths or isolated vertices. Let $\mathcal{ L}_{ n,k}$ be the family of all linear forests of order $n$ with $k$ edges. In this paper, we prove that \[ ex(n;\mathcal{ L}_{ n,k})= \max \left\{ \binom{ k}{ 2},\binom{ n}{ 2}-\binom{ n-\left\lfloor \frac{ k-1}{ 2}\right \rfloor}{ 2}+ c \right\}, \] where $c=0$ if $k$ is odd and $c=1$ otherwise. This determines the maximum number of edges in a non-Hamiltonian graph with given Hamiltonian completion number and also solves two open problems in \cite{ WY} as special cases. Moreover, we show that our main theorem implies Erd\H{ o}s-Gallai Theorem and also gives a short new proof for it by the closure and counting techniques. Finally, we generalize our theorem to a conjecture which implies the famous Erd\H{ o}s Matching Conjecture.
Categories: math.CO