Let $G$ be an $n$-vertex graph containing no path of length $k$. One can show (not that easy but doable) that $e(G) \leq \frac{k-1}{2}n$ (equivalently, the average degree $\bar{d}$ satisfies $\bar{d} \leq k -1$). I want to check that this bound is best for all $k$ with non-trivial examples.
If $k = 2m+1$, one can give an example of a connected, $\textbf{non-complete}$, graph containing no $P_k$ and with $\bar{d} \geq 2m - \varepsilon$ for any $\varepsilon > 0$. Indeed, the complete bipartite graph $K_{m,N}$ for some large $N$ has maximal path length $2m$ and its average degree is $\frac{2mN}{m+N}$ - easy to check that this is more than $2m - \varepsilon$ for large $N$.
Can anyone help me with an example of a connected, $\textbf{non-complete}$, graph, containing no $P_{2m}$ and with $\bar{d} \geq 2m - 1 - \varepsilon$ for any $\varepsilon > 0$?
A $d$-regular balanced tree of depth $h$. The diameter is $2\log(h)$, while you can make $d=\bar{d}$ arbitrarily large. In particular you can choose $d$ larger than a constant multiple of the diameter.