The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
3.5k 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}$
asked in Graph Theory by Veteran (68.8k points)
edited by | 3.5k views

2 Answers

+26 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}.$
answered by Veteran (14k points)
edited by
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 .

+13 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

answered by Veteran (58.7k points)
Nice ..


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

32,330 questions
39,146 answers
108,244 comments
36,501 users