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

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

Dark Mode

11,144 views

36 votes

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

- $n^2$
- $\frac{n(n-1)}{2}$
- $n-1$
- $\frac{(n+1)(n)}{2}$

1

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.

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.

0

43 votes

Best answer

1

0 votes

**Answer : B**

''maximum number of edges in a n-node undirected graph without self loops''

it means you have to make a complete graph , in complete graph there are edge between each node . you can't make two edge between between 2 edges , because in undirected graph it does't make sense.

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