Must a $30$-regular graph contain a path of length at least $20$?

Question

Let simple graph $G$ be a $30$-regular graph. Is it true that $G$ must contain a path of length at least $20$?

Answer 1

According to this survey paper, theorem 5.5, if a graph $G$ with $n$ vertices has no path of length $k\ge2$ then the number of edges of $G$ is $$e(G) \le \frac{k-2}{2}n$$ With $k=20$ this gives $e(G)\le9n$ but since $G$ is $30-$regular, we know $e(G)=15n.$ Thus, there must be a path of length $20$.

The paper gives no proof, but says that the theorem was proved by Erdös and Gallai here.

Answer 2

You don't need the full strength of Erdős-Gallai here. As @MichaelBurr indicates, we can be greedy. Being greedy means doing exactly what you think you should do.

Let's suppose we want to find this path in our graph: let's start a any old vertex. Now let's move to a new vertex along an edge in our graph. Let's move to another new vertex, and so on, making our path. Now how could we get stuck? That is, when can we no longer extend our path? Let's say we've made a path with $k$ vertices in it, and we want to extend it to a path of length $k+1$. If we are prevented from extending the path, it must be that all of the edges incident to an endpoint of our path must be incident to vertices already in our path, because a path cannot go through the same vertex twice. But again, when can this happen? Each vertex has $30$ edges incident to it, but our path only has length $k$. So if $30 \geq k$, we can extend our path! By this greedy argument, we can extend our path possibly until it has length $31$.