Proving Connectivity After Removing k Vertices in a Finite Graph

[Office_Shredder]

Homework Statement

If a finite connected graph G has minimal degree k, show there exists a path x_1, x_2, x_3,..., x_k so that G-{x_1,x_2,...,x_k} is still connected

Homework Equations

Minimal degree means every vertex has k or more edges connecting to it

The Attempt at a Solution

I'm pretty much nowhere. I can do by induction that you can remove k vertices without disconnecting G by the following:

You can pare G down to a spanning tree, and then it has a vertex you can remove from the tree (since it has to have a leaf). Remove that, and the tree is still connected, so when you add back the rest of the edges it's still connected. This new graph has minimal degree at least k-1 so there are k-1 other vertices you can remove.

I can't see how to make a path though (I tried a similar induction argument for a path but it's demonstrably false as far as I can tell)

 

[epenguin]

I think this is silly.

It has taken me since yesterday to realize.

If you can show, similarly to what you have, that you can remove an edge, x₁ say, without disconnecting, then you have a connected graph G - x₁ of minimal degree (k -1), so ...

 

[Office_Shredder]

So I can remove a path of length k-1. I have already demonstrated to myself that the path found is not necessarily one that can be extended to a path of length k, unless I missed something.

http://img21.imageshack.us/img21/8876/graphtheory.png

I need a way of finding the 'right' vertex to remove, so that a path can be removed of length k-1 that has an edge to the one I removed.

EDIT: Whoops, the graph in the picture has minimal degree k, not k+1. That's a typo