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?
Best Answer
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$.