1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graph Theory

  1. Oct 28, 2009 #1


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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 [tex] x_1, x_2, x_3,...., x_k[/tex] so that [tex]G-{x_1,x_2,...,x_k}[/tex] 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. jcsd
  3. Oct 30, 2009 #2


    User Avatar
    Homework Helper
    Gold Member

    :rolleyes: I think this is silly.

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

    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 ...
  4. Oct 30, 2009 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Graph Theory
  1. Graph Theory (Replies: 5)

  2. Graph theory (Replies: 0)

  3. Graph Theory (Replies: 0)

  4. Graph Theory (Replies: 4)