[proofplan] The strategy mirrors the [Ore-Dirac Hamiltonicity](/theorems/2036) proof but with a weaker degree hypothesis. Take a maximum-length path $x_1, \ldots, x_\ell$ in the connected graph $G$. Maximality forces $N(x_1), N(x_\ell) \subseteq \{x_2, \ldots, x_{\ell-1}\}$. The same pigeonhole on $N^-(x_1)$ and $N(x_\ell)$ — this time using $|N(x_1)|, |N(x_\ell)| \geq k/2$ and the ambient set of size $\ell - 1$ — yields $N^-(x_1) \cap N(x_\ell) \neq \varnothing$ whenever $\ell \leq k$, producing a cycle of length $\ell$. If $\ell = n$, we are done (a Hamilton cycle and hence a path of length $n - 1 \geq k$). Otherwise, connectivity provides a vertex adjacent to the cycle, extending the path beyond length $\ell$, contradicting maximality. Hence $\ell \geq k + 1$, i.e., the path has at least $k$ edges. [/proofplan] [step:Take a path of maximum length and locate neighbours of the endpoints on the path] Let $P: x_1, x_2, \ldots, x_\ell$ be a path in $G$ with the **maximum number of vertices**. Such a path exists because $G$ is finite. **Claim:** $N(x_1) \subseteq \{x_2, \ldots, x_\ell\}$ and $N(x_\ell) \subseteq \{x_1, \ldots, x_{\ell-1}\}$. *Proof of claim.* If $x_1$ had a neighbour $w \notin V(P)$, prepending $w$ to $P$ yields a path with $\ell + 1$ vertices, contradicting maximality. Since $x_1 \notin N(x_1)$ (no loops), $N(x_1) \subseteq V(P) \setminus \{x_1\} = \{x_2, \ldots, x_\ell\}$. The case of $x_\ell$ is symmetric. **Lower bound on $\ell$ from the degree hypothesis.** Since $\deg(x_1) \geq \delta(G) \geq k/2$ and $N(x_1) \subseteq \{x_2, \ldots, x_\ell\}$ (a set of $\ell - 1$ vertices), we have $\ell - 1 \geq k/2$, so \begin{align*} \ell \geq \frac{k}{2} + 1. \end{align*} This gives a lower bound but not yet the bound $\ell \geq k + 1$ we need. The remaining argument strengthens this via the cycle construction. [guided] The extremal argument — taking a longest path and observing that endpoints have no outside neighbours — is the same trick as in the proof of the [Ore-Dirac Hamiltonicity](/theorems/2036) theorem. Here the degree bound is $\delta \geq k/2$ rather than $\delta \geq n/2$, so the conclusion is weaker: we get a cycle of length at least $k + 1$ rather than a Hamilton cycle. The preliminary bound $\ell \geq k/2 + 1$ is far from $\ell \geq k + 1$. To close the gap we build a cycle of length $\ell$ (using pigeonhole, as in Ore-Dirac) and then argue that if $\ell \leq k$ the cycle could be used to extend the path by one vertex, contradicting maximality. [/guided] [/step] [step:Build a cycle of length $\ell$ via pigeonhole on $N^-(x_1)$ and $N(x_\ell)$] Define \begin{align*} N^-(x_1) := \{x_i \in V(P) : 1 \leq i \leq \ell - 1,\ x_{i+1} \in N(x_1)\}. \end{align*} The map $x_i \mapsto x_{i+1}$ is a bijection from $N^-(x_1)$ onto $N(x_1) \cap \{x_2, \ldots, x_\ell\} = N(x_1)$ (the latter by the endpoint claim). Hence $|N^-(x_1)| = |N(x_1)| \geq k/2$, and $N^-(x_1) \subseteq \{x_1, \ldots, x_{\ell-1}\}$. Both $N^-(x_1)$ and $N(x_\ell)$ are subsets of $\{x_1, \ldots, x_{\ell-1}\}$, a set of size $\ell - 1$. **Case analysis on $\ell$.** We claim that if $\ell \leq k$, we can derive a contradiction. Suppose $\ell \leq k$. Then by pigeonhole, \begin{align*} |N^-(x_1) \cap N(x_\ell)| \geq |N^-(x_1)| + |N(x_\ell)| - (\ell - 1) \geq \frac{k}{2} + \frac{k}{2} - (\ell - 1) = k - \ell + 1 \geq 1. \end{align*} So there exists $x_i \in N^-(x_1) \cap N(x_\ell)$: an index with $x_{i+1} \in N(x_1)$ and $x_i \in N(x_\ell)$. Construct the cycle \begin{align*} C: x_i,\ x_\ell,\ x_{\ell-1},\ \ldots,\ x_{i+1},\ x_1,\ x_2,\ \ldots,\ x_i \end{align*} by concatenating: the edge $x_i x_\ell$, the reversed path segment $x_\ell, x_{\ell-1}, \ldots, x_{i+1}$ (using edges $x_\ell x_{\ell-1}, \ldots, x_{i+2} x_{i+1}$), the edge $x_{i+1} x_1$, and the forward path segment $x_1, x_2, \ldots, x_i$ (using edges $x_1 x_2, \ldots, x_{i-1} x_i$). This is a cycle with $\ell$ distinct vertices and $\ell$ edges: a cycle of length $\ell$ through every vertex of $P$. [illustration:long-path-cycle-construction] [guided] The pigeonhole arithmetic is central: \begin{align*} |N^-(x_1) \cap N(x_\ell)| \geq \frac{k}{2} + \frac{k}{2} - (\ell - 1) = k - \ell + 1. \end{align*} When $\ell \leq k$, the right-hand side is $\geq 1$, so the intersection is non-empty. When $\ell \geq k + 1$, the inequality gives nothing (trivially $\geq 0$), but we do not need it: $\ell \geq k + 1$ is exactly the conclusion we want, and the cycle-building argument becomes unnecessary. **Cycle construction details.** See the proof of [Ore-Dirac Hamiltonicity](/theorems/2036) for the same rotation/reversal construction. Given the pair $(x_i, x_{i+1})$ where $x_i \in N(x_\ell)$ and $x_{i+1} \in N(x_1)$, the cycle uses all $\ell$ vertices of $P$ with $\ell$ edges: $\ell - 1$ edges of $P$ except $x_i x_{i+1}$, plus the two new edges $x_i x_\ell$ and $x_1 x_{i+1}$, giving $(\ell - 1) - 1 + 2 = \ell$ edges. **What have we achieved so far?** Assuming $\ell \leq k$, we have produced a cycle $C$ of length $\ell$ in $G$. The next step shows this is impossible: the combination of a cycle of length $\ell$ and the hypothesis $\ell < n$ allows us to extend $P$ beyond length $\ell$, contradicting maximality. [/guided] [/step] [step:Use connectivity to extend $P$ beyond $C$, deriving a contradiction with maximality] We now rule out $\ell \leq k$. Since $k < n$ by hypothesis and we have assumed $\ell \leq k$, we have $\ell < n$. So $V(G) \setminus V(C) \neq \varnothing$; pick $w \in V(G) \setminus V(C)$. Since $G$ is connected (given), there exists a path in $G$ from $w$ to some vertex of $C$. Follow a shortest such path; the first vertex of $C$ it reaches, call it $x_j$, is adjacent to some vertex $w^* \in V(G) \setminus V(C)$ on the path (in the degenerate case $w^* = w$, if $w$ is itself adjacent to $x_j$). Now construct a path in $G$: \begin{align*} Q: w^*,\ x_j,\ x_{j+1},\ x_{j+2},\ \ldots,\ x_{j-1}, \end{align*} where indices are taken modulo $\ell$ around $C$. This traverses the cycle $C$ starting at $x_j$, going all the way around (using $\ell - 1$ cycle edges), ending at $x_{j-1}$, and has $w^*$ as a prepended vertex. The total vertex count is $1 + \ell$, and the edge count is $1 + (\ell - 1) = \ell$. Since $w^* \notin V(C) = V(P)$, the path $Q$ has $\ell + 1$ vertices, strictly more than $\ell = |V(P)|$. This contradicts the maximality of $P$. Hence our assumption $\ell \leq k$ is false: $\ell \geq k + 1$, so $P$ has at least $k$ edges, i.e., length at least $k$. $G$ contains a path of length $k$. [guided] **Why does $Q$ have $\ell + 1$ distinct vertices?** $Q$ has $w^*$ at the start and then visits every vertex of $C$ exactly once. By assumption $w^* \notin V(C)$, so $w^*$ is distinct from all cycle vertices. The cycle vertices $x_j, x_{j+1}, \ldots, x_{j-1}$ (indices mod $\ell$) are distinct because $C$ is a cycle of length $\ell$ through $\ell$ distinct vertices. Total: $\ell + 1$ distinct vertices. **Why does $Q$ use valid edges?** The edges are: $w^* x_j$ (exists because $w^*$ is adjacent to $x_j$, by construction), $x_j x_{j+1}, x_{j+1} x_{j+2}, \ldots, x_{j-2} x_{j-1}$ (all edges of $C$ except $x_{j-1} x_j$ — we skip one cycle edge to open the cycle into a path). So we use $\ell$ edges. **Why does this contradict maximality of $P$?** $P$ was chosen to have the maximum vertex count among paths in $G$. $Q$ is a path with more vertices than $P$. Contradiction. Hence the supposition $\ell \leq k$ is untenable, forcing $\ell \geq k + 1$. **Conclusion.** The path $P$ has $\ell \geq k + 1$ vertices, equivalently $\ell - 1 \geq k$ edges. Since "length of a path" conventionally counts edges, $P$ has length $\geq k$. $G$ contains a path of length at least $k$. **Why was connectivity essential?** Without connectivity, a vertex $w \notin V(C)$ might be in a different component than $C$, and no path would connect them. The hypothesis "$G$ is connected" in the theorem statement is precisely what lets the extremal argument close. (Without connectivity, the theorem fails: a disjoint union of small cliques can have $\delta(G) \geq k/2$ but no path of length $k$ if each clique is smaller than $k$.) **Comparison with Ore-Dirac.** The [Ore-Dirac Hamiltonicity](/theorems/2036) theorem uses $\delta \geq n/2$ to force a Hamilton cycle — a path of length $n - 1$. Here we weaken the hypothesis to $\delta \geq k/2$ and obtain only a path of length $k$, which is weaker but still strong enough to be useful (e.g., for applications like the [Edge Count Forces Long Path](/theorems/2038) theorem that uses this result as a lemma). [/guided] [/step]