GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 8

Question

The maximum number of edges in a disconnected graph having $12$ vertices is _______

Answer 1

We get maximum edges in a disconnected graph of $n$ vertices when one vertex is isolated and remaining $n-1$ vertices are completely connected giving $\dfrac{(n-1)(n-2)}{2}$ edges. For $n=12,$ we get maximum $\dfrac{11\cdot 10}{2} = 55$ possible edges.

So, the correct answer is $55.$

Comments

Using $(n-1)$ vertices the maximum possible edges are $^{(n-1)}C_{2} = \dfrac{(n-1)!}{(n-3)!\cdot 2!} = \dfrac{(n-1)(n-2)(n-3)!}{(n-3)!\cdot 2\cdot 1} = \dfrac{(n-1)(n-2)}{2}$

---

Lakshman Patel RJIT

minimum no. of edges in a disconnected graph with 12 vertices is 0 ??

where there are 12 components & 0 edges

---

Yes.