edited by
1 flag 17,670 views
39 votes
39 votes

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}$
  • ๐Ÿšฉ Edit necessary | ๐Ÿ‘ฎ Nirbhay Chaubey | ๐Ÿ’ฌ โ€œThe question should mention that the graph is a simple graph, else it has infinitely many no. of edges.โ€
edited by
1 flag

8 Answers

Best answer
49 votes
49 votes
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$
edited by
18 votes
18 votes

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

0 votes
0 votes
maximum number of edges in a n-node undirected graph without self loops is   n(n-1)/2
0 votes
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

 

 

Answer:

Related questions

29 votes
29 votes
3 answers
1
Kathleen asked Sep 15, 2014
11,391 views
The performance of a pipelined processor suffers if:the pipeline stages have different delaysconsecutive instructions are dependent on each otherthe pipeline stages share...
76 votes
76 votes
12 answers
2
Kathleen asked Oct 4, 2014
34,435 views
The number of distinct simple graphs with up to three nodes is$15$$10$$7$$9$
8 votes
8 votes
1 answer
3
go_editor asked Jun 13, 2016
3,961 views
Consider the graph shown in the figure below:Which of the following is a valid strong component?$a, c, d$$a, b, d$$b, c, d$$a, b, c$
33 votes
33 votes
5 answers
4
Kathleen asked Oct 8, 2014
21,020 views
The minimum number of edges in a connected cyclic graph on $n$ vertices is:$n-1$$n$$n+1$None of the above