1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Ethan Bolker Feb 1 at 2:46
  • 1
    $\begingroup$ 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? $\endgroup$ – saulspatz Feb 1 at 4:07
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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