graph theory proof

prove that in a simple connected graph if every vertex has a degree at least m, then there is a path of length at least m

any hints? i made a path: v0 with deg=1, v1 with deg=2,...vm with deg=m. then said this path has a length of at least m and a degree of at least m.
i'm not sure if that is right?

Quote:

---

Originally Posted by mathh18

prove that in a simple connected graph if every vertex has a degree at least m, then there is a path of length at least m

any hints? i made a path: v0 with deg=1, v1 with deg=2,...vm with deg=m. then said this path has a length of at least m and a degree of at least m.
i'm not sure if that is right?

---

The basic idea is to construct the path inductively. In each step you can find a new vertex, which is not a neighbor of the vertices you've already used.

More in detail:
First, notice that the whole graph has at least m+1 vertices. (Do you know why?)

Start with any vertex v1. Choose any neighbor of it for v2.
If m=1 you're done.
If m>1 than v2 has a neighbor different from v1. (Otherwise the degree of v2 would be 1.) Choose any such neighbor for v3.

If you already have v1,v2,...,vk for some k<=m then:
Choose for v_{k+1} any of neighbors of vk different from v1,v2,...,v_{k-1}. Again such a vertex must exist, otherwise the degree of vk would be at most k-1, which is less than m.