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."(adsbygoogle = window.adsbygoogle || []).push({});

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!

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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?

Can you offer guidance or do you also need help?

**Physics Forums | Science Articles, Homework Help, Discussion**