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.

Prove that if $G$ is a graph with $n$ nodes and no loops or double edges and more than $\binom{n-1}{2}$ edges, then $G$ is connected.

This is an exercise in Lovasz' Discrete Mathematics book.

share|improve this question
3  
You need one more edge, i.e., $\dbinom{n-1}2+1$. –  user17762 Apr 24 '13 at 17:55
2  
You also need that there are no loops or double edges. Maybe that is part of your definition of a graph, sometimes that is a simple graph. –  Ross Millikan Apr 24 '13 at 18:00
    
Oops. Thanks user17762. –  user43666 Apr 24 '13 at 18:00

1 Answer 1

up vote 3 down vote accepted

You need one more edge, i.e., $\dbinom{n-1}2+1$. The proof falls out immediately using contradiction. Assume that the graph is disconnected. We can then find two sets of vertices $A$ and $B$ with no edges running between them. The maximum number of edges in this graph is $$\vert E \vert = \dbinom{n_A}2 + \dbinom{n_B}2$$ where $n_A \geq 1$ is the number of vertices in $A$, $n_B \geq 1$ is the number of vertices in $B$ with $n_A + n_B = n$. We then have $$\vert E \vert = \dfrac{n_A(n_A-1) + n_B(n_B-1)}2 = \dfrac{n_A^2 + n_B^2-n}2$$ Find the maximum of this function with the constraint $n_A, n_B \geq 1 $ and $n_A + n_B = n$. I trust you can take it from here.

share|improve this answer
    
Yes, thank you. –  user43666 Apr 24 '13 at 18:02

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.