# Let $G$ be a graph with $n$ vertices where every vertex has a degree of at least $\frac{n}{2}$. Prove that G is connected.

First question, if the problem uses a fraction such as $$\frac{n}{2}$$, would we round down in case $$n$$ is odd?

As for the actual problem, I'm trying to do this with induction and contrapositive and was wondering if my methods are correct. I'm also wondering if anyone can give a proof by contradiction, I feel like it would be pretty similar to a proof by contrapositive but can't quite put my finger on it.

Induction

A base case of $$n=2$$ gives a degree of one for all vertices.

Assume $$G$$ with $$n$$ vertices where every vertex has a degree of at least $$\frac{n}{2}$$ is connected.

Show that $$G$$ with $$n+1$$ vertices has a degree of at least $$\frac{n+1}{2}$$ is connected.

If we remove a vertex $$v$$, then by the inductive hypothesis, the graph is connected.

Now we add the $$v$$ back in. We now need to ensure that $$v$$ and all the other vertices have at least a degree of $$\frac{n+1}{2}$$. This means that we need to connect $$v$$ to the other vertices.

It follows that $$G$$ is connected.

Contrapositive

Prove that if $$G$$ is disconnected, then $$G$$ cannot be a graph with $$n$$ vertices where every vertex has a degree of at least $$\frac{n}{2}$$.

Assume that $$G$$ is disconnected.

We can then examine the case where there are the smallest number of connected components - $$2$$.

Each one can have at most $$\frac{n}{2}$$ vertices. Thus, each vertex can have a degree of at most $$\frac{n}{2}-1$$ since it cannot connect to itself.

It follows that this is a contradiction and $$G$$ is connected.

• The Contrapositive you gave is a proof by contradiction. – shai horowitz May 16 '16 at 0:09
• @shai horowitz I thought a proof by contrapositive is one such that if you were trying to prove the statement $P \implies Q$ you could instead do $\sim Q \implies \sim P$ ? – Justin Liang May 16 '16 at 0:11
• To answer your first question, no, you’d round up. At least $\frac{n}2$ means $\ge\frac{n}2$, so if $n=5$, for instance, each vertex has degree $\ge\frac52$ and therefore, since the degree is an integer, $\ge 3$. – Brian M. Scott May 16 '16 at 0:11

## 3 Answers

Hardmath's answer gives the correct proof, but I wanted to also answer your first question and point out the problems with the proofs you posted.

"At least $\frac{n}{2}$" means "$\geq \frac{n}{2}$," so if $\frac{n}{2}$ is not an integer, you know the degree of each vertex is actually greater than $\frac{n}{2}$ (i.e., round up, not down).

There's a problem with your inductive proof - if you remove a vertex, a priori the remaining vertices have degree at least $\frac{n+1}{2}-1=\frac{n-1}{2}$, but this is smaller than $\frac{n}{2}$, so the induction hypothesis is not satisfied.

There is also a problem with your contrapositive proof. First you don't justify why you can only consider the case of two connected components. You also say each connected component can have at most $\frac{n}{2}$ vertices. What if one has $\frac{n}{4}$ vertices and the other $\frac{3n}{4}$? As noted in hardmath's answer, you only need the fact that some connected component has no more than $\frac{n}{2}$ vertices (and then you don't need to consider the case of only two connected components).

Suppose $G$ is not connected and has $n$ vertices. Some component of $G$ then has at most $n/2$ vertices. A vertex in this component then has degree at most one less, i.e. $\lt n/2$.

To make this a "proof by contradiction" we need only begin with assuming $G$ has degrees at least $n/2$ for every vertex.

Pick two vertices $u,v$ in $G$.

If there is an edge $uv$ you are done. Otherwise, $u$ is connected to at least $\frac{n}{2}$ of the remaining $n-2$ vertices. Same way $v$ is connected to at least $\frac{n}{2}$ of the remaining $n-2$ vertices.

By the pigeon hole principle, $u$ and $v$ must be connected to a common vertex $w$.

P.S. This shows something stronger, namely that $G$ has a diameter of at most 2.