Hi I need major help with these types of proving questions concerning connections and graphs. For this particular question I know you can prove using contradiction i.e when $G$ is not connected and there exists some vertices in $G$ with degree at most $n/2$. But I am not clear of the steps to take to prove that if there is such a vertice then the graph is still connected.
Help will be greatly appreciated!:))
Best Answer
Your on the right way. Assume that $G$ isn't connected, then it has at least 2 connected components. So by Pigeonhole Principle there exists a connected component, say $H$ with at most $\frac n2$ vertices. So now take $v \in V(H)$. Then by the assumption has a degree of at least $\frac n2$. But these edges are all in $H_1$, which is impossible as $H_1$ has at most $\frac n2$ vertices.