0
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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... $\endgroup$ Commented Feb 23, 2021 at 15:54
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Feb 23, 2021 at 16:17
  • 4
    $\begingroup$ 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. $\endgroup$ Commented Feb 23, 2021 at 17:06

1 Answer 1

0
$\begingroup$

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?

$\endgroup$

You must log in to answer this question.

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