# How to approach Graph Theory Proofs

Show that if $$G$$ is a simple graph with $$n$$ vertices (where $$n$$ is a positive integer) and each vertex has degree greater than or equal to $$n−1$$, then the diameter of $$G$$ is $$2$$ or less.

I ended up getting very stuck on this question. Proving by contradiction is usually how I go about getting a better understanding of what is actually being asked for but when I tried this one I ended up doing something with the neighbors of the vertices and I just got off on the wrong track. How would you have approached this question and in general what are things to look out for with proofs like this?

• Diameter 2 means that any two vertices are either connected directly, or have a path between them via one other vertex. Suppose there are two vertices that are not directly connected, then... Commented Feb 23, 2021 at 15:54
• Can you draw such a graph for small $n$ like $3, 4, 5$? This might tell you what you expect $G$ to look like in general. Commented Feb 23, 2021 at 16:17
• Unless I am misunderstanding something the question seems trivial. As there are only $n$ vertices and the graph is simple, the degree of each vertex must be exactly $n-1$ and hence there is an edge joining each distinct pair of vertices so the diameter is 1. Commented Feb 23, 2021 at 17:06

Hint. (Assume $$n \ge 2$$.) If every pair of two points is connected by an edge, the diameter is $$1$$.
Now, suppose two points $$v$$ and $$w$$ are not connected by an edge. Let $$V_v$$ and $$V_w$$ denote the set of vertices connected to $$v$$ and $$w$$, respectively. If $$V_v \cap V_w \neq \varnothing$$, then you are done. (Why?)
Note that $$|V_v|, |V_w| \ge n - 1$$. (Why?)
On the other hand, $$|V_v \cup V_w| \le n$$. Thus, we have $$|V_v \cap V_w| = |V_v| + |V_w| - |V_v \cup V_w| \ge 2(n-1) -n = n - 1 \ge 1.$$ Can you conclude now?