The problem consists of three parts, but I could only figure out the very first part:
Suppose that $G$ is a simple graph with $n\ge2$ vertices and at least $\frac{(n-1)(n-2)}{2}+1$ edges.
(a) Show that G cannot cantain an isolated vertex.
(b) Suppose that $n\ge3$, and that $G$ is not connected. Show that removing any vertex from $G$ will result in a graph with at least $\frac{(n-2)(n-3)}{2}+1$ edges.
(c) Using the results in (a) and (b), prove by induction that $G$ must be connected.
I proved (a) by contradiction, explaining that if an isolated vertex exists in $G$, $G$ would have at most $\frac{(n-1)(n-2)}{2}$ edges.
However, I have no idea how to proceed to step (b). I couldn't even come up with a $G$ that satisfy the conditions of (b).
Any suggestions? Thanks a lot.
Best Answer
(b) Any vertex is connected to at most $n-2$ edges because $G$ is not connected so $\frac{(n-1)(n-2)}{2}+1-(n-2)=\frac{(n-2)(n-3)}{2}+1$
(c) Suppose $G$ with $n$ vertices is not connected and have at least $\frac{(n-1)(n-2)}{2}+1$ edges then remove a vertex we have a not connected graph with $n-1$ vertices and at least $\frac{(n-2)(n-3)}{2}+1$ edges contradicting our induction hypothesis for $n-1$ case.