Question

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.

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