GATE CSE 2002 | Question: 1.25, ISRO2008-30, ISRO2016-6

Question

The maximum number of edges in a $n$-node undirected graph without self loops is

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

Comments

It should be connected,simple, undirected graph. Else answer is INFINITE.

A simple graph means no self-loop and no parallel edges. 

---

Use recursion;
Start with building a base case, T(1) =0, ie, 1 node can have 0 maximum edges;

degree of new node = edges due to new node;
T(2) = 1 + T(1); // degree of node added to already existing number of edges, T(2) = 1
T(3) = 2 + T(2); // degree of new node added is 2 as for the previous case we had a graph of 2 nodes, T(3) = 3

Similarly, T(n) = T(n-1) + n-1. Now the relation can be solved.

---

max no. of edegs without self loop and parallel edges are  n*(n-1)/2
but when we add self loop n vertices can have n self loop so add +n to above formula
and you will get
 

Ans – D

Answer 1

If we consider edges between each vertex it will be $^nC_2 = \frac{n(n-1)}{2}$. answer will be (B)

Answer 2

max no. of edegs without self loop and parallel edges are  n*(n-1)/2
but when we add self loop n vertices can have n self loop so add +n to above formula
and you will get
 

Ans – D

Answer 3

Since the graph is undirected (v1,v2) is same as (v2,v1).So we care only about picking a pair and placing an edge between them without any self loops and multiple edges as simple undirected graph is needed

No of ways to pick a pair from n objects =nC2=n(n-1)/2

 

Correct answer is option B.

Answer 4

 maximum number of edges in a n-node undirected graph without self loops is complete graph.

 

so, no. of edges in complete graph = nC2 = n(n-1)/2

I hope my answer helps you a lot.