1. ## Graphy Theory Question about Blocks

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!

2. ## Re: Graphy Theory Question about Blocks

Originally Posted by Johnyboy
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.
You need to provide some definitions.
What is a block?
What does $\delta(G)$ stand for?

3. ## Re: Graphy Theory Question about Blocks

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.

4. ## Re: Graphy Theory Question about Blocks

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.