Path Length

**Len** · February 10th 2011, 11:07 AM

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

**PaulRS** · February 11th 2011, 05:06 AM

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 ?

**Len** · February 11th 2011, 01:15 PM

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 ?

Thanks for the reply.

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

**PaulRS** · February 13th 2011, 07:35 AM

Originally Posted by Len

Thanks for the reply.

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<k$ )

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.

Thread: Path Length

LinkBack

Thread Tools

Display

Path Length

Similar Math Help Forum Discussions

[SOLVED] Finding length of path over an interval

Finding path length of curve

Length needed from a known length and angle

degree of a path, path homotopy.

arc length and parameterized curve length

Search Tags