11,144 views

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

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

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

In a graph of $n$ vertices you can draw an edge from a vertex to $\left(n-1\right)$ vertex we will do it for n vertices so total number of edges is $n\left(n-1\right)$ now each edge is counted twice so the required maximum number of edges is $\frac{n\left(n-1\right)}{2}.$

Correct Answer: $B$

But the question disallows only self loops , parallel edges may be present.
I have not considered parallel edge because it will lead to infinity which is not in option

The correct answer is ∞, but if we assume that the graph is Simple (i.e self-loop and parallel edges are disallowed) then the ans will be (b) n(n-1)/2 .

how

For maximum no of edges we must have one edge for each pair of vertices.

We can select a pair out of N nodes in NC2 ways = N(N-1)/2

by

Nice ..
@debashish

For directed graph , maximum no of edges would be n^2 -n ??

Yes @Satyajeet

For simple directed graph , maximum no of edges would be n^2 -n.

maximum number of edges in a n-node undirected graph without self loops is   n(n-1)/2

''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

1
9,122 views