I'm trying to pick up a little graph theory out of Bondy and Murty's Graph Theory as suggested here.
Problem 1.1.12 has given me a little hitch.
Let $G$ be a simple graph of order $n$ and size $m$. (So there are $n$ vertices and $m$ edges). If $m>\binom{n-1}{2}$, then $G$ is connected.
I'm following a hint in an appendix which says if $G$ is not connected, we can partition the vertices into parts $(X,Y)$ such that no edge joins a vertex in $X$ to a vertex in $Y$. What is the largest number of edges in $G$ if $|X|=r$ and $|Y|=n-r$?
I suppose the graphs on $X$ and $Y$ are then complete graphs, for a total of $\binom{r}{2}+\binom{n-r}{2}$ edges. Simplifying, this is $\frac{2r^2+n^2-2rn-n}{2}$, so I'm trying to show $$ \frac{2r^2+n^2-2rn-n}{2}\leq\frac{(n-1)(n-2)}{2} $$ to get the contrapositive.
The above is equivalent, if my algebra is correct, to showing $r\geq\frac{n-1}{n-r}$ for any $0\lt r\lt n$. This seems reasonable, but I can't quite show it. How would I do so? Thanks.
I'd also be happy to see a solution that doesn't necessarily make use of the hint.
