# Connected Graphs

I want to know if you could could help me in establishing a proof for connected graphs?

The question is prove that a finite graph $$G= (V,E)$$ satisfying the inequality $$|E|> \frac{(|V|-1)(|V|-2)}{2}$$ is connected.

I have the basic knowledge of what a finite graph is and what a connected graph is but I do not know how to start the proof.

• Welcome to stackexchange. Please edit the question to show us what you have tried and where you are stuck. Perhaps begin with a graph with a small number of vertices ($4$ or $5$) and see what happens when you have fewer edges than your hypothesis demands. – Ethan Bolker Feb 1 at 2:46
• Try proof by contradiction. If the graph is not connected, it has at least two connected components. What is the maximum number of edges it can have? – saulspatz Feb 1 at 4:07

Assume it's not connected. Then it's separated in at least two components, namely, $$a_1$$ and $$a_2$$. It satisifies $$|a_1|+|a_2|=|V|$$. Then $$E\le\frac{ a_1\cdot(a_1+1)+a_2\cdot(a_2+1)}2\le\frac{(|V|-1)(|V|-2)}{2}$$ with equality occur iff $$|a_1|=1$$ or $$|a_2|=1$$. This is because if $$n=a+b=c+d$$, then $$(n-k)(n-k+1)+k(k+1)$$ is maximised when $$k$$ is minimized or maximised. Try prove the last one by yourself.