10
$\begingroup$

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.

  • 1
    I think the title of your question would've been better as "Is a graph $G=(V,E)$ with |E| > \binom{|V|-1}2 connected?"2012-11-11

1 Answers 1

12

$ \begin{align*} r &\ge \frac{n-1}{n-r}\\ rn-r^2 &\ge n-1\\ rn-r^2-n+1 &\ge 0\\ (r-1)n-(r-1)(r+1) &\ge 0\\ (r-1)(n-r-1) &\ge 0 \end{align*} $

  • 0
    Quick and clean, thank you.2011-04-21