Proving a graph is connected by minimum degree

5.7k Views Asked by At

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?

1

There are 1 best solutions below

0
On

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.