# Thread: Path Length

1. ## Path Length

Prove that if G is a simple graph with minimum degree k, where k $\displaystyle \geq$ 2 then G has a path of length at least k.

I've been bouncing through ideas all day but I keep finding flaws in them. I feel like I must show that G is hamiltonian but I do not know how to do that.

Any help is appreciated, plus rep like always.

Thanks

2. Let $\displaystyle x_1,...,x_r$ be the longest simple path in the graph, and suppose (we want to get a contradiction) that $\displaystyle r < k$.

What happens with the neighbours of $\displaystyle x_r$ ? Do they all appear in the path ?

3. Originally Posted by PaulRS
Let $\displaystyle x_1,...,x_r$ be the longest simple path in the graph, and suppose (we want to get a contradiction) that $\displaystyle r < k$.

What happens with the neighbours of $\displaystyle x_r$ ? Do they all appear in the path ?
Thanks for the reply.

So $\displaystyle x_r$ would have to be connected to at least k points(min degree). Since $\displaystyle r \geq k+1$ because r is connected to k points and then we add the r point itself. Therefore $\displaystyle r > k$ which is a contradiction of $\displaystyle r < k$ and hence G has a path length of at least k.

This makes more sense, if I'm wrong please correct me but thanks again!

PS PaulRS as in the creator of RS? :P

4. Originally Posted by Len
Thanks for the reply.

So $\displaystyle x_r$ would have to be connected to at least k points(min degree). Since $\displaystyle r \geq k+1$ because r is connected to k points and then we add the r point itself. Therefore $\displaystyle r > k$ which is a contradiction of $\displaystyle r < k$ and hence G has a path length of at least k.

This makes more sense, if I'm wrong please correct me but thanks again!

PS PaulRS as in the creator of RS? :P
( first I should have written $\displaystyle r\leq k$ and not $\displaystyle r<k$ )

Well, if the path had length $\displaystyle k-1$ or less, then there'd be at most $\displaystyle k$ nodes in the path but then $\displaystyle x_r$ has a neighbour that is none of the others in the path, thus we would be able to extend the path (adding the new node at the end) contradicting the maximality of the length of the path.

PS: No, it's my initials.