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.

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.