Hi how would you go about solving the following question:
Prove that if G is a graph of order n >= 3 with delta(G) >= n/2, then G is a block.
Thanks!
A block is a maximal connected non-separable graph, stated differently a connected graph that contains no cut-vertices and is not properly contained in a subgraph with no cut-vertices and delta(G) = min{deg v: v in V(G)}. Thanks.
I tried an approach using induction but I got stuck. I did the following:
Start of induction process:
Let n=3, then delta(G) >= n/2, it follows that the lowest degree of a vertex is 2. Therefore G has no end-vertices, therefore G is not a tree and G must contain at least one cycle C_k. It follows that since the order of G is 3, G is the cycle C_3 and is therefore a block.
Assume that n > 3 and the result is true for graphs of order less than n.
My idea is to take a graph of order n with delta(G) >= n/2 and then remove some vertex v, which gives us a graph G-v of order n-1 with delta(G-v) >= (k-1)/2, apply the induction hypothesis to conclude that G-v is a block and then show that if we add vertex v again then G is still required to be a block.
One of my main problems is that I am not sure how to specify the vertex v that I want to remove in order to ensure that G-v satisfies delta(G-v) >= (k-1)/2 so that I can use the inductive hypothesis.