Results 1 to 2 of 2

Math Help - connectivity 3 regular graph

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    51

    connectivity 3 regular graph

    if a graph G is 3 regular prove that vertex connectivity=edge connectivity
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2008
    Posts
    1,034
    Thanks
    49
    From any edge cut set you can build a corresponding vertex cut set with as many or fewer vertices, so vertex connectivity is never larger than edge connectivity. And if you build the other way round you'll only need more edges than vertices if any vertex (in your original cut set) is connected by two edges into each block. (Making it at least degree 4.)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Edges and Connectivity
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 3rd 2011, 04:55 AM
  2. 3-Regular graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 16th 2010, 04:34 AM
  3. Graph connectivity proofs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 12th 2010, 12:11 PM
  4. 4-regular Graph
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 19th 2009, 04:49 PM
  5. Graph Theory - Edge Cut / Connectivity
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: July 6th 2009, 04:52 AM

Search Tags


/mathhelpforum @mathhelpforum