Self Doubt

Question

If a graph with n vertices has more than $\left ( n-1 \right )\left ( n-2 \right ) / 2$ edges then it is connected.

I am a bit confused about this question, since I can always prove that for a graph to connected you need more than $\geq n-1$ edges.

Comments

yes you can but how will you confirm that these 4 edge are connected with each vertices. I can connect 4 vertices with 4 edges but does it mean that it is connected? No.

see read the statement one more time you only know the number of edges and no of vertices so to confirm whether it is connected or not you need more than (n-1)(n-2)/2 edges.

---

Are this statement correct

Minimum number of edges required for simple graph to be coonected i==> N - 1

A graph with N-1 edges is need not be connected

A graph having atleast (N-1)(N-2)/2 edges is always connected

---

1) True

2) True

3) not atleast but more than and for undirected graph.

Answer 1

Let us consider a 5 vertices graph,

use every edge for 4 vertices , we know number of edges possible for a 4 vertices regular graph is the complete graph k4,

we have  used up 6 edges, and to connect to the final vertex you need one more edge.

Thus for this graph to be connected you must use more than 6 edges {(5-1)(5-2)/2}

which on generalizing results to the formula in question.

*Equivalent statement would be , for n vertices consider edges more than required in k(n-1); which is C(n-1,2)