Results 1 to 2 of 2

Math Help - Graph Theory Proof

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    16

    Graph Theory Proof

    Prove the following claim:

    In an undirected and unweighted graph with k vertices, If the length of the shortest path between vertices u and v is greater than k/2 then there must be a vertex w not equal to u or v whose removal disconnects u and v.

    I want to do some kind of proof involving the Pigeonhole Principle to show that multiple paths between u and v must share at least one vertex (whose removal would disconnect u and v), but I can't seem to make it work. Any ideas?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Haven's Avatar
    Joined
    Jul 2009
    Posts
    197
    Thanks
    8
    Suppose for a contradiction that the result doesn't hold.

    So, if we remove a vertex, then there is another path from u to v in the graph. So, it follows that these two paths must create a cycle.

    If the paths are internally disjoint (all vertices apart from u and v are distinct), then by hypothesis, each path is of length greater than k/2. So, the cycle has more than k vertices, which cannot happen.

    So, any two paths between u and v must share at least one internal vertex

    this should be enough to get you started.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 11th 2010, 11:00 PM
  2. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 7th 2010, 11:59 AM
  3. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 5th 2010, 08:34 AM
  4. Graph theory: proof
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: October 29th 2009, 12:00 PM
  5. Graph Theory Proof Help
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 4th 2009, 02:52 PM

Search Tags


/mathhelpforum @mathhelpforum