# Examples to show that the edge-bound for no paths of length $k$ is best

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.