How to prove that the diameter of a graph is less than 2 given that the minimum degree of any vertex in G is greater than the number of vertices / 2

Question

How do I prove the following statement.

Let $G = (V,E)$ be a graph. Prove that if $δ(G) \ge \frac{|V|}2$, then $\operatorname{diam}(G) \le 2$

I believe $\delta$ is minimum degree of any vertex in $G$ and diam is the largest shortest path.

I thought that I would try to prove this statement by contradiction, assume $δ(G) < |V|/2$. But then I'm stuck because I don't understand how to reach a contradiction in this case to prove the original statement true. Do I attempt to plug in a value for $δ(G)$ such that my assumed expression holds and then try drawing figures that don't represent my assumption to prove a contradiction or is there something else I'm missing?

Answer 1

It's probably easiest to do this directly.

Assume $\delta(G) \geq \frac{|V|}{2}$ and pick two vertices that aren't adjacent. What would you need to prove about the neighbourhoods (the sets of vertices adjacent to them) to guarantee that they're distance $2$ apart?

Answer 2

To prove "If $A$ then $B$" by contradiction, you cannot start "Assume not $A$ ...". You might start with "Assume not $B$" and try to show "not $A$" from it.

But a direct proof is possible: Let $u,v$ be any two distinct vertices of a graph with $\delta(G)\ge \frac{|V|}2$. We proceed to show that the distance from $u$ to $v$ is at most $2$. If $uv$ is an edge, we are done. Hence assume $uv$ is not an edge. Then the neighbours of $u$ and the neighbours of $v$ are subsets of $V\setminus\{u,v\}$ of cardinality $\ge \frac12|V|$, hene cannot be disjoint. If $w$ is in the intersection then $uwv$ is a paath of length $2$ from $u$ to $v$.