A few days ago I began a foray into graph theory on a whim, using a discrete mathematics book that I picked up a while ago. I'd like a HINT for this problem, if someone would be so inclined as to provide me with one.
Let $G$ be a graph of order $n$. Prove that if $\delta(G) \ge \frac{1}{2}(n-1)$, then $G$ is connected.
Here $\delta(G)$ is the minimum degree of $G$. In a previous problem I obtained a sharp bound of $\frac{1}{2}(p-1)(p-2)$ for the size of a disconnected graph. I wanted to take $\frac{1}{4}n(n-1)$ as the minimum number of edges of $G$ ($\frac{1}{2}(n-1)$ per vertex times $n$ vertices times $\frac{1}{2}$ to account for sharing) and take (using $q$ as the size of $G$) $q \ge \frac{1}{4}n(n-1) \ge \frac{1}{2}(n-1)(n-2)$, then use induction to show that the last inequality held true, forcing $q$ above the upper bound for a disconnected graph.
It would have been very nice if this had actually worked. Unfortunately, I didn't test the inequality very far, and it fails to hold already at $n=5$.
Any hints (not answers!) are most appreciated. Thanks!