# Graphs of diameter 2

How can I prove that $$G$$ (a simple graph) having diameter $$2$$ and maximum degree $$\Delta(G)=n-2$$ has $$m\geq 2n-4$$, where $$n$$ is the number of vertices and $$m$$ is the number of edges.

This doesn't look like a very hard problem, I don't know why but it confuses me a lot. I would really like to see how one should solve it (since I'm self-studying graph theory I think most of my proofs tend to be kind of ad hoc and messy).

• Is $\Delta(G)$ the maximum degree in $G$?
– Paul
Apr 10, 2013 at 7:24
• @Paul: Yes, it is. Apr 10, 2013 at 7:31

Let $v$ be a vertex of degree $n - 2$ and let $w$ be the unique vertex not adjacent to $v$. Every neighbor of $w$ is also a neighbor of $v$. Since $G$ has diameter exactly $2$, $w$ is adjacent to some neighbor of $v$. Let $s = \deg(w)$. Because $G$ has diameter $2$, each of the $n - 2 - s$ neighbors of $v$ that are not neighbors of $w$ must be adjacent to some neighbor of $w$. Hence, there are a total of at least $$(n - 2) + s + (n - 2 - s) = 2n - 4$$ edges in $G$.