GATE CSE 2002 | Question: 1.25, ISRO2008-30, ISRO2016-6
in Graph Theory edited by
9,605 views
34 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}$
in Graph Theory edited by
9.6k views

1 comment

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

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

0

Subscribe to GO Classes for GATE CSE 2022

5 Answers

41 votes
 
Best answer
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

4 Comments

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

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 .

1
how
0
16 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

by

3 Comments

Nice ..
0
@debashish

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

Yes @Satyajeet

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

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

 

 

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

Related questions

Ask
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true