in Graph Theory recategorized by
1,183 views
1 vote
1 vote
The maximum number of edges in a n-node undirected graph WITH self-loops is?
in Graph Theory recategorized by
1.2k views

4 Comments

if more than one self loops are allowed then answer can be infinity $\infty$
2
2
yes, but at least they have to mention each vertex has "k" self loops or these many number of vertices have self loops...
1
1

i agree question should have been more precise because Pseudograph can contain any number of self loops for every vertex.

1
1

1 Answer

4 votes
4 votes
Best answer
If the graph is without self-loop,

then to determine the maximum no,. of edge

We need to select $2$ node from $n$ nodes i.e. $^nC_2$ or $\dfrac{n(n-1)}{2}$

But, The question tells us to find out the maximum no. of edge of a graph without self-loop

Now, Every vertex is having $(n+1)$ edge in an undirected graph having $n-$ nodes & with self-loop

(Assuming every vertex is having a self-loop )

If we take a universal vertex which is having a degree  $(n-1)$ & we know that a self-loop is contributing $+2$ (both in-degree & out-degree) degree in a universal or dominating vertex.

As the graph has $n$- vertex, ∴ there can be maximum $n$-loops.

∴$\color{green}{\text{Maximum no. of edges }}$= $n + ^nC_2$

$\qquad  \qquad =n +\bigg \{\dfrac{n!}{2! \times (n-2)!}\bigg\}$

$\qquad  \qquad =n + \bigg\{\dfrac{n \times (n-1) \times (n-2) \times .....}{2! \times (n-2)!}\bigg\}$

$\qquad \qquad =n+ \dfrac{n(n-1)}{2} $

$\qquad \qquad =\dfrac{n(n-1) + 2n}{2}$

$\qquad \qquad  =\dfrac{n(n-1 + 2)}{2}$

$\color{purple}{\qquad \qquad =\dfrac{n(n+1)}{2}}$
edited by
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