UGC NET CSE | December 2010 | Part 2 | Question: 4

Question

The minimum number of edges in a connected graph with $‘n’$ vertices is equal to

• A. $n (n – 1)$ 
• B. $\frac{n(n-1)}{2}$
• C. $n^{2}$
• D. $n – 1$

Answer 1

Ans: D

The minimum number of edges for undirected connected graph is (n-1) edges.

For the maximum number of edges (assuming simple graphs), every vertex is connected to all other vertices which gives arise for n(n-1)/2 edges (use handshaking lemma).

Answer 2

The minimum number of edges in a connected graph with n vertex is n-1 i.e. Tree.

D is answer