Results 1 to 6 of 6

Math Help - Is there such a graph?

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Is there such a graph?

    Is there a graph that is 1-connected and 3-connected, but not 4-connected? Why?

    First off, can someone give the definition of being 1,3,or 4 connected in 'English'. All the def. are so technical and I don't really understand.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by jzellt View Post
    Is there a graph that is 1-connected and 3-connected, but not 4-connected? Why?

    First off, can someone give the definition of being 1,3,or 4 connected in 'English'. All the def. are so technical and I don't really understand.
    Intuitively a graph G=\left(V,E\right) is, say 2-connected (i.e. biconnected) if it has no, what is called "articulation points". These are points for which you can take away and leave the graph disconnected. In other words, no matter what vertex you take away from G it remains connected. Think of this as a network flow having redundancies. If a server goes down there are other serves which still connect all the mainframes, and thus everything stays connected.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Feb 2008
    Posts
    535
    So let me make sure I understand you correctly. Say G is 3 connected. This means I can pick and remove and 2 vertices and G will remain connected. But If I remove 3, then G will be disconnected. Correct?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by jzellt View Post
    So let me make sure I understand you correctly. Say G is 3 connected. This means I can pick and remove and 2 vertices and G will remain connected. But If I remove 3, then G will be disconnected. Correct?
    Eh....it means that no matter which two vertices you remove the resulting graph will be connected. It says nothing about three vertices.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Feb 2008
    Posts
    535
    So, does the complete graph on 4 vertices meet my requirements? I can remove 1 vertex - still connected. I can remove 3 vertices - still connected. But If I remove 4 vertices, then I have no more graph...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Feb 2008
    Posts
    535
    I'm pretty sure that the graph I described above works. Are there others? Thanks.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  2. Replies: 7
    Last Post: August 5th 2011, 01:30 PM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 03:30 AM
  4. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  5. Replies: 1
    Last Post: February 15th 2009, 05:35 AM

Search Tags


/mathhelpforum @mathhelpforum