Erdos-Gallai Theorem

If we want the Extremal Graph number for Path $P_k$ (path with $k$ edges, or $k+1$ vertices), then it is at most $(k-1)n/2$.

This bound is almost tight. It will be tight if $n$ is a multiple of $k$. We can have $G$ be a union of complete graphs $K_k$. If that happens, the as all the connected components of size $k$, we will never have a connected subgraph with $k+1$ vertices. Then by Handshake Lemma and that $G$ is $(k-1)$-regular, there are $(k-1)n/2$ edges.

Also recall that the extremal graph need not be connected. We are simply trying to maximize the number of edges.

Proof:

Let $G$ be an $n-$vertex graph with at least $(k-1)n/2$ edges. We prove by strong induction on $n+k$ that $G$ contains $P_k$ unless every component of $G$ is $K_k$.

If $G$ is disconnected, then we can examine each piece individually. Suppose some component of $G$ contains a path of length $k$ or equals $K_k$. We remove it and get a graph with $n-k$ vertices with the following edges:

$$\frac{(k-1)n}{2}-\frac{k(k-1)}{2}=\frac{(k-1)(n-k)}{2}$$

edges. By induction, that graph is a union of $K_k$ or contains a path of length $k$, and we are done.

Therefore we can assume $G$ is connected. If $k=1$, then a single edge forms $P_1$. If there are no edges, then every component is $K_1$. Let $k\ge 2$. If $G$ contains a vertex $v$ degree less than $k/2$, then $G^{\prime }=G-\{v\}$ has at least

$$|E(G^{\prime })|>\frac{(k-1)n}{2}-\frac{k}{2}=\frac{(k-1)(n-1)}{2}$$

edges remaining. Since $G^{\prime }$ still has enough edges, by induction it must contain a path $P_k$ or be a union of $K_k$. Since $G^{\prime }\subset G$, then the same holds for $G$.

Thus, $\delta (G)\ge k/2$. By induction, $G$ contains a path $P$ of length $k-1$. Let this be from $u\to w$. All $N(u),N(v)\subseteq P$, otherwise we could just extend the path $P$ and be done. By lemma¹, we have a cycle $C$ of length $k$ containing $P$.

If there is a vertex $x\notin C$, and as $G$ is connected, there must be a path from $x\to C$, and in particular, adding edge $(w,x)$ with $w\in V(C)$, we get a path of length $k$ ending with $x$. Thus $V(C)=C(G)$ and so $|V(G)|=k$ and $G=K_k$ as required.

This proof is almost entirely copied verbatim from the Verstraete textbook.

Erdos-Gallai Conjecture

If $T$ is any Tree with $k$ edges, then

$$\text{ex}(n,T)\le \frac{(k-1)n}{2}$$

The above Erdos-Gallai Theorem was used to prove this for paths specifically.

Footnotes

1. This is also known as Dirac’s Theorem. ↩