How to prove a simple graph is 2-connected?

  • Thread starter cxc001
  • Start date
  • #1
16
0
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!
 

Answers and Replies

Related Threads on How to prove a simple graph is 2-connected?

  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
6
Views
2K
Replies
2
Views
549
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
1
Views
946
Replies
1
Views
1K
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
6
Views
642
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
3K
Top