# Connected/disconected graph vis-a-vis number of edges

I have doubt regarding the following:-(n=number of vertices)

1) Minimum number of edges for a graph to be connected = n-1

2) maximum number of edges for a graph to be disconnected or to stay disconnected(not able to form correct wording. Please correct me here. I mean there is disconnected graph. I will keep on adding edges till it remain disconnected. I am thinking about how many maximum edges be there and still remain disconnected) = $$\binom{n-1}{2}$$

## My approach for (2)

Say graph is disconnected and there be 2 components. Then number of edges = $$\binom{n_1}{2}+\binom{n_2}{2}, n_1, n_2$$ are vertices in 1st and 2nd component respectively($$n_1+n_2=n$$). For edges to be maximum, gap between n1 and n2 has to be maximum for its sum constant. So n1 = 1 and n2 = n-1 or vice-versa. So in this case, the num of edges become $$\binom{n-1}{2}$$

Please correct me if i am wrong above both in (1) and (2)

• I guess $1)$ is true and it have special name tree. – emonHR Nov 23 '19 at 18:46
• sir can u please have a look at this now? – Nascimento de Cos Nov 23 '19 at 19:58

## 1 Answer

$$1)$$ is true and it has special name tree.
$$2)$$ I think number of edges may vary from graph to graph. Since you consider the graph is not connected it has at least two components. Even if it has more than $$2$$ components, you can think about it as having $$2$$ "pieces", not necessarily connected.

Let $$k$$ and $$n-k$$ be the number of vertices in the two pieces. Then, each vertex in the first piece has degree at most $$k-1$$, therefore the number of edges in the first component is at most $$\frac{k(k-1)}{2}$$, while the number of edges in the second component is at most $$\frac{(n-k)(n-k-1)}{2}$$.

To finish the problem, just prove that for $$1 \leq k \leq k-1$$ we have $$\frac{k(k-1)}{2}+ \frac{(n-k)(n-k-1)}{2} \leq \frac{(n-1)(n-2)}{2}$$

You can also prove that you only get equality for $$k=1$$ or $$k=n-1$$.

• sir can u please explain how u got that last inequality? – Nascimento de Cos Nov 24 '19 at 7:30
• It's from your assumption $\binom{n-1}{2}$ which bound all possible. – emonHR Nov 24 '19 at 7:56
• Got it sir. Thank you ...... – Nascimento de Cos Nov 24 '19 at 7:57
• I am glad to help you – emonHR Nov 24 '19 at 7:59