If G is a connected graph with 100 vertices, and each vertex has at least degree 10, then prove that there is a path with at least 21 vertices in G
How can I solve this problem? I know it has something to do with the fact that 21 is around 10 times 2
Here is an algorithm to construct such a path.
First, start with a single edge and greedily extend it in both directions. That is, for as long as you can add another edge to either end of the path which doesn't visit a previously used vertex, do so.
When we're done, we have a path on vertices $v_0, v_1, v_2, \dots, v_k$, visiting them in exactly this order, such that all neighbors of $v_0$ and $v_k$ are also on the path (or else we could extend it). We may assume that $k < 20$, because if $k\ge 20$, we are done.
Let $S \subseteq \{1,2,\dots,k\}$ be the set of indices $i$ such that $v_0$ is adjacent to $v_i$, and let $T \subseteq \{1,2,\dots,k\}$ be the set of indices $i$ such that $v_{i-1}$ is adjacent to $v_k$. Because the graph has minimum degree $10$, and all neighbors of $v_0$ and $v_k$ are on the path, we have $|S|\ge 10$ and $|T|\ge 10$.
But $S$ and $T$ together are contained in a set of size less than $20$. So there is no room for them to be disjoint: there must be an index $i \in S\cap T$, meaning that $v_0$ is adjacent to $v_i$ and $v_{i-1}$ is adjacent to $v_k$. This turns our path into a cycle: $v_0, v_1, \dots, v_{i-1}, v_k, v_{k-1}, \dots, v_i, v_0$.
Since the graph is connected and has more than $k+1$ vertices, at least one vertex on this cycle must have a neighbor $w$ outside $\{v_0, v_1, \dots, v_k\}$. This lets us make a longer path: start at $w$, take the edge to the cycle, and then walk all the way around the cycle.
Now go back to the first step, extending this path greedily, and repeat. This algorithm lets us keep going for as long as the path has fewer than $21$ vertices, so it stops when it finds a path on $21$ vertices or more.
This algorithm generalizes in two ways: