# Graphy Theory Question about Blocks

• Aug 21st 2012, 11:39 AM
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.(Thinking)

Thanks!
• Aug 21st 2012, 11:47 AM
Plato
Re: Graphy Theory Question about Blocks
Quote:

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.(Thinking)

You need to provide some definitions.
What is a block?
What does $\displaystyle \delta(G)$ stand for?
• Aug 21st 2012, 12:01 PM
Johnyboy
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.
• Aug 21st 2012, 12:03 PM
Johnyboy
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.