Lower and upper bound for the maximal number of edges of a graph

Question

I am looking for a proof of the lower and upper bound for the maximal number of edges of a graph that does not contain the path $P_{r}$ with $1 \leq r < n$.

Answer 1

We have a lower bound of $\binom n2 - \binom{n-s}{2}$ or equivalently $\binom s2 + s(n-s)$ for $s = \lfloor \frac {r-1}{2}\rfloor$. That's the closest thing to your $\binom n2 - \binom r2$ bound that's actually true.

To prove this, let $v_1, v_2, \dots, v_n$ be the vertex set and take all the edges with at least one endpoint in $\{v_1, v_2, \dots, v_s\}$. Then the longest path in this graph has $2s$ edges, because every edge of the path must be incident to at least one of $v_1, \dots, v_s$, and each of those vertices can be used at most twice. In other words, this graph does not contain $P_{2s+1}$.

Note that $\binom s2 + s(n-s)$ simplifies to $\frac{r-1}{2}(n-1)$ when $r$ is odd, which is close to your upper bound. Another way to get close is to take $\lfloor\frac nr\rfloor$ disjoint $r$-cliques. These have $\binom r2 \cdot \frac nr = \frac{n(r-1)}{2}$ edges when $n$ is divisible by $r$; fewer, otherwise.

---

For the upper bound, a graph with at least $\frac{n(r-1)}{2}$ edges is a graph with average degree at least $r-1$. We may assume it's connected (otherwise, we may pass to the densest connected component) and we may assume that it has minimum degree $\frac{r-1}{2}$ (deleting a vertex with degree less than $\frac{r-1}{2}$ increases the average degree). The graph will always have at least $r$ vertices to maintain an average degree of at least $r-1$.

Once we have a connected graph with minimum degree $\frac{r-1}{2}$ and at least $r$ vertices, we can find a path of length $r$ by emulating the proof of Dirac's theorem. (Briefly, take a maximal path. If it is shorter than length $r$, we can use it to create a cycle, which extends to a longer path by connectivity. Then repeat.)