1. Not finding help here? Sign up for a free 30min 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!

How to prove a simple graph is 2-connected?

  1. Sep 17, 2010 #1
    Problem: "Let G be a simple graph on n vertices such that deg(v)>= n/2 for every vertex v in G. Prove that deleting any vertex of G results in a connected graph."

    Well, I tried to find the min. case.

    Let k be the min. deg. of vertex in a simple graph,
    n is number of vertices in G
    so k = min{deg(v)} and k >= n/2,

    I found the boundary for n is in [k+1, 2k] to satisfy the given inequality constraint.
    n >=2 and k >=1

    besides the very first case when k=1 and n=2, which is P2, a connected walk with two vertices and one edge,
    the rest of the cases when n>=3 and k>=2 are exactly 2-connected graph

    BUT HOW CAN I PROVE IT IS TO BE EXACTLY 2-CONNECTED GRAPH THOUGH?

    If I can prove it is a 2-connected graph, then for any two vertices of G, there is a cycle containing both.

    Then by deleting any vertex of a 2-connected graph would result in a connected graph. Since for any two edges of G, there is a cycle containing both.

    I can either use the definition of 2-connected graph to prove it or maybe use induction to prove it at last.

    Any suggestion would be really helpful!
     
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?



Similar Discussions: How to prove a simple graph is 2-connected?
  1. Graph theory, prove (Replies: 0)

Loading...