# Graph Theory

1. Oct 28, 2009

### Office_Shredder

Staff Emeritus
1. The problem statement, all variables and given/known data

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

2. Relevant equations

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

3. 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)

2. Oct 30, 2009

### epenguin

I think this is silly.

:uhh: It has taken me since yesterday to realise.

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

3. Oct 30, 2009

### Office_Shredder

Staff Emeritus
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 [Broken]

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

Last edited by a moderator: May 4, 2017