Let $n \geq 2$ and $p \geq 1$ be two positive integers. Let $G$ be a graph with n vertices such that each vertex has $p$ or more incident edges. Prove that if $p > \frac{n−2}2$ then $G$ is connected.
I'm not sure how to tackle this one.
- I guess that the Handshaking lemma might be relevant.
- I guess that it might be easier to prove the contrapositive?
Thanks to the helpers!
Proof by Contradiction, Let $G_{1}$ and $G_{2}$ be two component of $G$. Let $n$ is even then take $ n = 2m \geq 2$ then $m \geq 1$. We need to find maximum possible degree of a vertex in both component $G_{1}$ and $G_{2}$. WLOG we can take $|G_{1}| = |G_{2}| = m $ then maximum possible degree of $G_{1}$ or $G_{2}$ is $m-1$. Also we have from given condition that $p > \frac{n-2}{2} = m-1$ Contradiction. Hence there must be edges between $G_{1}$ and $G_{2}$. Graph is connected. Now Let $n = 2m+1$ be odd. Then take $|G_{1}|=m$ and $|G_{2}|=m+1$ and find maximum degree in both component. We get Maximum degree of $G_{1}$ as $m-1$ and same for $G_{2}$ as $m$. Now minimum degree $p > \frac{2m+1-2}{2} = m-1 + \frac{1}{2}$ i.e. $p \geq m$ and we will not get this in $G_{1}$. Contradiction. Hence Connected.