Graph Theory- show maximum number of edges in a simple graph [duplicate]

$\begingroup$

Show that the maximum number of edges in a simple graph with n vertices is $\frac{n(n-1)}{2}$ ?

$\endgroup$ 1

2 Answers

$\begingroup$

I got an answer.

We have that is a simple graph, no parallel or loop exist. Therefore the degree of each vertex will be one less than the total number of vertices (at most). ie, degree=n-1

eg. we have a graph with two vertices (so one edge) degree=(n-1).

(n-1)=(2-1)=1

We know that the sum of the degree in a simple graph always even ie, $\sum d(v)=2E$

here d(v)=n-1 : we have n vertices the total degree is n(n-1)

n(n-1)=2E

E=$\frac{n(n-1)}{2}$

Thank you all.

$\endgroup$ $\begingroup$

HINT (?): Draw it. Each $n$ must be connected to all other $n's$. You will also use double-counting.

$\endgroup$