Question

# Let G be an n-vertex graph with n ≥ 2 and δ(G) ≥ (n-1)/2. Prove that...

Let G be an n-vertex graph with n ≥ 2 and δ(G) ≥ (n-1)/2. Prove that G is connected and that the diameter of G is at most two.

#### Homework Answers

Answer #1

SOLUTION

Suppose that G is not connected. So, there exists two vertices u and v which lie in different components. Now, since both u and h have degree at least (n-1)/2, so the component in which they lie have at least (n-1)/2 + 1 vertices at least. Thus, total number of vertices in both the components is at least (n-1)/2 + 1 + (n-1)/2 + 1 = n+1.

Clearly this is a contradiction as there are n vertices in total. So, G must be connected.

Suppose G have diameter >2. So, there exists two vertices u and v such that uv path has length > 2. Thus, u and v share no common neighbours.

Now, since both u and h have degree at least (n-1)/2, so total number of neighbours of u and v combined are (n-1)/2 + (n-1)/2 = n-1

This implies that total number of vertices in the graph is n-1 + 2 = n+2 which is a contradiction. So, diameter must be <= 2.

Please Upvote

Thank you

Know the answer?
Your Answer:

#### Post as a guest

Your Name:

What's your source?

#### Earn Coins

Coins can be redeemed for fabulous gifts.

##### Not the answer you're looking for?
Ask your own homework help question
ADVERTISEMENT
##### Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

ADVERTISEMENT