- #1

- 16

- 0

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!