# Proving a graph is connected by minimum degree

Let number of vertices be $\ge 2$. If the min degree of G $\ge \frac n2$, then the graph is connected.

I was trying to solve this using contradiction, but now I'm stuck. So I started out with "If the the min degree of G $\ge \frac n2$, then the graph is disconnected. This means there are at least two components. Any help?

• If you know about Ore's theorem you can use it, because if $\forall v\in V \ deg(v)\geq \frac{n}{2}$ then $G$ is Hamiltonian and that means it must be connected. – Mateusz Sep 4 '14 at 14:34

It's important to setup a contradiction by first assuming the statement does not hold - that is, assuming its negation. In this case, the negation is not

"min degree at least $n/2 \Rightarrow G$ is disconnected"

as you started off with, but rather

"min degree at least $n/2$ DOES NOT IMPLY that $G$ is connected"

These are different and it's important to make the distinction.

So assume that having min degree >= $n/2$ does not imply that $G$ is connected. Then that means there exists a graph $G$ with min degree >= $n/2$ such that $G$ is disconnected.

Let $X$ be the smallest connected component of $G$ (the one with the least vertices). You can work out that $X$ has at most $n/2$ vertices. Take a vertex $x$ of $X$. Now, $x$ can have at most $n/2 - 1$ neighbors in $X$, so $x$ must have a neighbor outside of $X$. You should then see the contradiction.

Assume that $G$ is a disconnected with $n$ vertices ($|G|=n$). Then, there are at least 2 disconnected subgraphs of $G$. Let us call them $X$ and $Y$. Without loss of generality, let us assume that $|X|\leq|Y|$ i.e. $X$ has at most the same amount of vertices of $Y$.

Hence, $|X|\leq \frac{n}{2}$. Now every vertex in $X$ can connect to at most all the other vertices in $X$ (none in $Y$ since it is disconnected from $X$, and we say at most since $X$ could be made of many disconnected components itself).

Therefore, for any vertex $u\in X$, $deg(u)\leq \frac{n}{2}-1<\frac{n}{2}$.

Finally $\delta(G)\leq \delta (X) \leq deg(U)<\frac{n}{2}$.

i.e. if $\delta(G) \geq \frac{n}{2}$ then $G$ is connected.