Let G be a simple graph with n vertices. Prove that if the degree of every vertex is at least $\frac{n-1}2$, then G is connected.

I've tried the degree sum formula, but it doesn't seem to get me anywhere. Below is my attempt.
$\sum_{v\in V}deg(v) \ge \frac{n(n-1)}2$
$|E| \ge \frac{n(n-1)}4$

There's something about the value $\frac{n-1}2$ that catches my attention. Intuitively it means that for every vertex $v \in V$, $v$ is connected to at least $half$ of the other $n-1$ vertices. But I don't know how to proceed from there.


Take two vertices $v_1 \neq v_2$. I'll show they are in the same connected component of the graph.

If they are connected then $v_1$ and $v_2$ are in the same connected component and we are done. So assume henceforward that they're not connected. Then there are $n-2$ points of the graph left, and $d(v_1) \ge \frac{n-1}{2}$ of them are neighbours of $v_1$, and $d(v_2) \ge \frac{n-1}{2}$ are neighbours of $v_2$. If these sets of neighbours were disjoint, we'd have $2\frac{n-1}{2} = n-1$ many remaining points, contradiction.

So they have a common neighbour, and thus a path between $v_1$ and $v_2$ exists.

  • $\begingroup$ Elegant and concise. Thanks! $\endgroup$ – Vizuna Nov 23 '14 at 13:12
  • $\begingroup$ @Vizuna Happy to help! $\endgroup$ – Henno Brandsma Nov 23 '14 at 13:13

Let $v \neq w$ be two vertices. I show that $v,w$ are connected by a path with at most 2 edges.

In fact, consider $Adj(v) = \{ u : (u,v) \mbox{ is an edge} \}$, and $Adj(w) = \{ u : (u,w) \mbox{ is an edge} \}$. If $v \in Adj(w)$ or $w \in Adj(v)$, then we are done.

Otherwise, $v \notin Adj(w)$ and $w \notin Adj(v)$. Since the graph is simple, we have $v \notin Adj(v)$ and $w \notin Adj(w)$, so $Adj(v) \cup Adj(w) \subseteq G \setminus \{ v,w \}$. But now

$$|Adj(v)|+|Adj(w)| \geq \frac{n-1}{2} + \frac{n-1}{2} = n-1 > |G \setminus \{ v,w \}| $$

Hence these two sets have nonempty intersection. Let $u \in Adj(v) \cap Adj(w)$. Then the path $(v,u), (u,w)$ connects the two vertices.

In particular this shows that $G$ is a connected graph.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.