$G$ is a connected graph with $100$ vertices, where vertices have minimum degree $10$. Show G has a path with $21$ vertices.
I know that for a graph with minimum degree $n$, there has to be a path of length of $n-1$. But with a connected graph of $n$ vertices, all I can think of is that it has to have at least $n-1$ edges (since tree is the minimal connected graph). Is there a connection between minimum edges and degree and path length?
Best Answer
Let $P = \langle v_1, \ldots, v_m \rangle$ be the longest path of $G$. Since $P$ is the longest path, $N(v_1)$ and $N(v_m)$ are subsets of $\{v_1,\ldots,v_m\}$. (Otherwise $P$ is not the longest path.)
If there exist $i \in \{2,\ldots ,m-2 \} $, such that $v_i \in N(v_m)$ and $v_{i+1} \in N(v_1)$, then the vertices of $P$ forms a cycle in $G$. (Why?) Since $G$ is connected, $P$ must connect to other vertices (If there's no other vertices, then $m = 100$.) This contradicts to the maximality of the length of $P$.
Hence if $i \in \{2,\ldots ,m-2 \}$ with $v_i \in N(v_m)$, we get $v_{i+1} \notin N(v_1)$. $\quad (*)$
Our goal is to show $m \geq 21.$ Suppose $m \leq 20$, then $N(v_1) \subseteq \{v_2,v_3,\ldots,v_{m-1}\}$. Note that $|\{v_2,v_3,\ldots,v_{m-1}\}| = (m-1)-2+1 = 18$. But $(*)$ restricts $9$ vertices in $\{v_3,v_4,\ldots,v_{m-1}\}$ can't adjacent to $v_1.$ This implies $|N(v_1)| \leq 18-9 = 9,$ which leads to a contradiction. This is our desired result.
Extra Exercise: Use this method to show the general result: