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?

  • $\begingroup$ 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. $\endgroup$
    – 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.


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.