Results 1 to 2 of 2

Math Help - Graph theory Problem

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    296

    Graph theory Problem

    A theorem says that a graph G of order 3+ is connected iff G has two distinct vertices u and v such that G-u and G-v are connected.

    Is it true then that Every connected graph G or order 4+ is connected iff G has three distinct vertices u, v, and w such that G-u, G-v, and G-w are connected?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Sep 2009
    Posts
    4
    A path of length n>=4 is a counterexample.

    ---
    proxximus
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 18th 2010, 09:36 PM
  2. Graph Theory problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 9th 2009, 01:50 PM
  3. Graph Theory Problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 16th 2009, 10:33 AM
  4. A graph theory problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 15th 2009, 12:08 PM
  5. Help with Graph Theory problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 2nd 2008, 11:08 PM

Search Tags


/mathhelpforum @mathhelpforum