Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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?" –  kahen Nov 11 '12 at 7:53

1 Answer 1

up vote 8 down vote accepted

$$ \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*} $$

share|improve this answer
    
Quick and clean, thank you. –  yunone Apr 21 '11 at 2:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.