7
$\begingroup$

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).

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

1 Answer 1

8
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Thank you, this is a nice proof. $\endgroup$
    – hannahh
    Apr 11, 2013 at 5:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .