# Connected Graph With Minimum Degree

$$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|\}$$.

• 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? – james black May 4 at 15:08
• 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)$. – Jerry Chang May 4 at 15:12
• so the fact that the graph has 100 vertices doesnt have antyhing to do with the question? – james black May 4 at 15:13
• We can get the same conclusion if $|G| \geq 21$. – Jerry Chang May 4 at 15:16
• 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 – james black May 4 at 15:18