[proofplan] We prove the statement by strong induction on the number of vertices $n$, with the small case $k = 1$ dispatched separately as an edge exhibits a path of length $1$. For $k \geq 2$, we reduce to the connected case by showing that some component must itself exceed the edge-density threshold. Within a connected graph, we split on the minimum degree: if $\delta(G) \geq k/2$, the [Minimum Degree Forces Long Path](/theorems/2037) theorem produces a path of length $k$ directly; otherwise, a low-degree vertex can be deleted while preserving an edge bound that is strong enough for the inductive hypothesis on $n - 1$ vertices to apply. [/proofplan] [step:Dispatch the base case $k = 1$ and the vertex base case $n = 2$] If $k = 1$, the hypothesis $e(G) > \frac{n \cdot 0}{2} = 0$ forces at least one edge, which is itself a path of length $1$. For $k \geq 2$ we proceed by strong induction on $n$. The smallest admissible $n$ is $n = 2$: the hypothesis $e(G) > \frac{2(k-1)}{2} = k - 1 \geq 1$ requires $e(G) \geq 2$, which is impossible on $2$ vertices (since $e(K_2) = 1$). Hence the base case is vacuous and there is nothing to verify when $n = 2$. Note that in any case the hypothesis $e(G) > \frac{n(k-1)}{2}$ combined with $e(G) \leq \binom{n}{2} = \frac{n(n-1)}{2}$ gives $n(k-1) < n(n-1)$, hence $k < n$. We therefore work under the standing assumption $k < n$ throughout. [/step] [step:Reduce to the connected case by passing to a high-density component] Assume the theorem holds for all graphs on fewer than $n$ vertices, and let $G$ be a graph on $n$ vertices with $e(G) > \frac{n(k-1)}{2}$. Suppose $G$ is disconnected, with connected components $C_1, \ldots, C_r$ of sizes $n_1, \ldots, n_r$ where $n = n_1 + \cdots + n_r$ and each $n_i < n$. Since edges occur only within components, \begin{align*} \sum_{i=1}^{r} e(G[C_i]) \;=\; e(G) \;>\; \frac{n(k-1)}{2} \;=\; \frac{k-1}{2} \sum_{i=1}^{r} n_i. \end{align*} By the pigeonhole principle (a strict inequality on a sum of positive quantities forces at least one summand to exceed the corresponding term on the right), there exists an index $i \in \{1, \ldots, r\}$ with \begin{align*} e(G[C_i]) \;>\; \frac{n_i (k - 1)}{2}. \end{align*} Since $n_i < n$, the inductive hypothesis applied to the subgraph $G[C_i]$ produces a path of length $k$ in $G[C_i] \subseteq G$, and we are done. [guided] We wish to reduce to the connected case because our two main tools — the theorem [Minimum Degree Forces Long Path](/theorems/2037) and the deletion step — both behave best on connected graphs. The mechanism is a pigeonhole argument on edge densities across components. Assume strong induction: the theorem holds for every graph on $n' < n$ vertices. Let $G$ on $n$ vertices satisfy $e(G) > \frac{n(k-1)}{2}$, and suppose $G$ has connected components $C_1, \ldots, C_r$ with $|C_i| = n_i$, so $\sum_i n_i = n$. Because edges lie entirely within components, \begin{align*} \sum_{i=1}^{r} e(G[C_i]) \;=\; e(G) \;>\; \frac{n(k-1)}{2} \;=\; \frac{k-1}{2} \sum_{i=1}^{r} n_i \;=\; \sum_{i=1}^{r} \frac{n_i(k-1)}{2}. \end{align*} A sum that exceeds another sum term-by-term must have at least one summand strictly larger than the corresponding summand on the right: if $e(G[C_i]) \leq \frac{n_i(k-1)}{2}$ for every $i$, summing would contradict the displayed inequality. Hence some component $C_i$ satisfies $e(G[C_i]) > \frac{n_i(k-1)}{2}$. Why is the inductive hypothesis applicable? We need $n_i < n$, and this holds as long as $G$ has more than one component — which is our assumption here. The inductive hypothesis then delivers a path of length $k$ inside $G[C_i] \subseteq G$, and hence a path of length $k$ in $G$. The remainder of the proof therefore assumes $G$ is connected. [/guided] [/step] [step:Apply the minimum-degree criterion when $\delta(G) \geq k/2$] Now assume $G$ is connected. If $\delta(G) \geq \frac{k}{2}$, we invoke the [Minimum Degree Forces Long Path](/theorems/2037) theorem. Its hypotheses require: (i) $G$ connected — verified; (ii) $n \geq 3$ — since $k \geq 2$ and $k < n$, we have $n \geq 3$; (iii) $k < n$ — verified in Step 1; (iv) $\delta(G) \geq k/2$ — our case hypothesis. The theorem produces a path of length $k$ in $G$. [/step] [step:Delete a low-degree vertex when $\delta(G) < k/2$ and apply the inductive hypothesis on $n - 1$ vertices] Otherwise $\delta(G) < \frac{k}{2}$, so there exists a vertex $x \in V(G)$ with \begin{align*} \deg_G(x) \;\leq\; \left\lfloor \frac{k-1}{2} \right\rfloor \;\leq\; \frac{k-1}{2}. \end{align*} (We use $\deg(x) < k/2$, which for an integer degree means $\deg(x) \leq \lceil k/2 \rceil - 1 \leq (k-1)/2$ since $k \geq 2$.) Deleting $x$ removes exactly $\deg_G(x)$ edges, so the subgraph $G - x$ on $n - 1$ vertices satisfies \begin{align*} e(G - x) \;=\; e(G) - \deg_G(x) \;>\; \frac{n(k-1)}{2} - \frac{k-1}{2} \;=\; \frac{(n-1)(k-1)}{2}. \end{align*} Since $n - 1 < n$, the inductive hypothesis applied to $G - x$ yields a path of length $k$ in $G - x$, which is a path of length $k$ in $G$. [guided] The case split in the previous step handled graphs with uniformly high minimum degree. Here we handle the complementary case, where some vertex is thin. The idea is simple: if $x$ has few edges, deleting it barely hurts the edge count, and we can afford the deletion within the inductive bound. Suppose $\delta(G) < k/2$. Then there is a vertex $x$ with $\deg_G(x) < k/2$. Since degrees are integers, this means \begin{align*} \deg_G(x) \;\leq\; \left\lceil \frac{k}{2} \right\rceil - 1. \end{align*} For $k \geq 2$, one checks that $\lceil k/2 \rceil - 1 \leq (k-1)/2$ in both parities: if $k = 2m$ is even, $\lceil k/2 \rceil - 1 = m - 1 \leq m - \tfrac{1}{2} = (k-1)/2$; if $k = 2m+1$ is odd, $\lceil k/2 \rceil - 1 = m = (k-1)/2$. Hence $\deg_G(x) \leq (k-1)/2$. Now delete $x$: the resulting graph $G - x$ has $n - 1$ vertices, and $e(G - x) = e(G) - \deg_G(x)$. Using the edge bound on $G$ and the degree bound on $x$, \begin{align*} e(G - x) \;=\; e(G) - \deg_G(x) \;>\; \frac{n(k-1)}{2} - \frac{k-1}{2} \;=\; \frac{(n-1)(k-1)}{2}. \end{align*} This is precisely the edge-density hypothesis of the theorem on $n - 1$ vertices. Since $n - 1 \geq 2$ (we have $n \geq 3$ from Step 3's verification) and $n - 1 < n$, the inductive hypothesis applies to $G - x$ and returns a path of length $k$. That path lives inside $G - x \subseteq G$, so it is a path of length $k$ in $G$. The induction is complete. [/guided] [/step]