Graph Book

Question

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

Comments

if more than one self loops are allowed then answer can be infinity $\infty$

---

yes, but at least they have to mention each vertex has "k" self loops or these many number of vertices have self loops...

---

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

Answer 1

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}}$