$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?


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:

Every connected graph $G \neq K_2$ contains a path or a cycle of length at least $\min\{2 \delta(G), |G|\}$.

  • $\begingroup$ oh yes, i came upn this the only question is this gives me 10*2=20 not 21, how would i add in the extra one? $\endgroup$ – james black May 4 at 15:08
  • $\begingroup$ Use this : If $i \in \{ 2 , \ldots, l-2\}$ with $v_i \in N(v_l)$, we get $v_{i+1} \not\in N(v_l)$. This restricts some possibilities of the vertices in $N(v_0)$ and $N(v_l)$. $\endgroup$ – Jerry Chang May 4 at 15:12
  • $\begingroup$ so the fact that the graph has 100 vertices doesnt have antyhing to do with the question? $\endgroup$ – james black May 4 at 15:13
  • $\begingroup$ We can get the same conclusion if $|G| \geq 21$. $\endgroup$ – Jerry Chang May 4 at 15:16
  • 1
    $\begingroup$ wow thats very cool thanks for your help, just one last question: could you elaborate a little bit on restricting the possibilities, i dont quite understand $\endgroup$ – james black May 4 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.