1. ## Path Length

Prove that if G is a simple graph with minimum degree k, where k $\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 $x_1,...,x_r$ be the longest simple path in the graph, and suppose (we want to get a contradiction) that $r < k$.

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

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

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

So $x_r$ would have to be connected to at least k points(min degree). Since $r \geq k+1$ because r is connected to k points and then we add the r point itself. Therefore $r > k$ which is a contradiction of $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

So $x_r$ would have to be connected to at least k points(min degree). Since $r \geq k+1$ because r is connected to k points and then we add the r point itself. Therefore $r > k$ which is a contradiction of $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 $r\leq k$ and not $r )

Well, if the path had length $k-1$ or less, then there'd be at most $k$ nodes in the path but then $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.