How to prove a simple graph is 2-connected?

[cxc001]

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!

 

[lippyka]

Proof by induction:Base case:Let G be a simple graph with n=2 vertices and let deg(v) >= 1, then G is a connected graph.Induction hypothesis:Assume that for any simple graph G with n vertices such that deg(v) >= n/2, deleting any vertex of G results in a connected graph.Inductive Step:Let G be a simple graph with n+1 vertices such that deg(v) >= (n+1)/2, then deleting any vertex of G will result in a connected graph.Proof: Let v be the vertex in G that is to be deleted. Then there must be at least one edge incident to v, so that there are at least n/2 edges left in the graph. By removing v, the remaining n vertices form a graph G' with n vertices and each vertex in G' has degree greater than or equal to (n-1)/2. By the induction hypothesis, G' must be connected after deleting v, thus G is also connected after deleting v. Therefore, the statement holds true for G. Hence, by mathematical induction, we can conclude that deleting any vertex of a simple graph G on n vertices such that deg(v)>= n/2 for every vertex v in G results in a connected graph.