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)

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

$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$.

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

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.