Let $k\in \mathbb{Z}_+.$ Prove that if $G = (V,E)$ is a connected graph with $|E| > {k^k \choose 2},$ then $G$ has a vertex of degree at least $k$ or contains a path with $k$ edges.
It suffices to show that if $G$ does not have a vertex of degree at least $k$, then $G$ contains a path with $k$ edges. However, I'm not sure how to find this path. I tried considering a few small cases such as $k=1,2,$ but I'm not sure how to generalize the result. For instance, for $k=1, G$ clearly contains at least two vertices and a path with $1$ edge (the path between those two distinct vertices). If $k=2, |E| > 6$, and by connectedness of $G$, there must be a vertex of degree at least $k$; if all vertices are of degree one, since $G$ is connected, it can only have two vertices and one edge, but then the number of edges is not more than $6$, a contradiction. I should definitely use the connected property, but I'm not sure how; for $k=2,$ if $G$ is disconnected, the proposition clearly fails.
Best Answer
I'll lay out an approach / hint in the first part, and then complete the proof in the second part of the post.
We can assume $k>1$. If $G$ has a vertex of degree $k$, we are done. So we assume that the maximum degree of $G$ is some $\Delta \leq k-1$.
We let $u$ be a vertex of $G$, and assume for the sake of contradiction that $G$ does not contain any path of length $k$. In particular, this means that the diameter of $G$ is at most $k-1$ (since $G$ is connected and has no $k$-path), so every vertex of $G$ is within distance $k-1$ of $u$ (this is where connectivity is useful!).
If you just wanted a hint / way to approach the problem, stop reading here.
Now given the degree and distance constraints we have so far, let's see how many vertices $G$ can have. We introduce the notation:
$$N_i(u) = \{v\in G : d(u,v) = i\}$$ The vertex $u$ has at most $(k-1)$ neighbours at distance $1$ from it (i.e., we have $|N_1(u)| \leq k-1$). Each of these in turn has at most $(k-2)$ neighbours besides $u$. So the set $N_2(u)$ of vertices distance $2$ from $u$ has $|N_2(u)| \leq (k-1)(k-2)$ (see the diagram).
In general, we get that $|N_i(u)| \leq (k-1)(k-2)^{i-1}$. So the total number of vertices $n$ is bounded above as follows:
$$n = |\{u\}| + |N_1(u)| + \dots + |N_{k-1}(u)|$$
And thus:
$$n \leq 1 + (k-1) + (k-1)(k-2) + \dots + (k-1)(k-2)^{k-2} = 1 + (k-1)\sum_{i=0}^{k-2}(k-2)^i$$
By using the formula for the sum of a geometric series, and a bit of inequality juggling, you can show that $n \leq k^k$. Thus the total possible number of edges that $G$ has is at most $\binom{n}{2} \leq \binom{k^k}{2}$. But this yields a contradiction, so $G$ must have a $k$-path.