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


    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?