I found that the maximum number of edges in a simple graph is equal to $$\sum\limits_{i=1}^{n-1} i$$

Where $n =$ number of vertices.

For example in a simple graph with $6$ vertices, there can be at most $15$ edges. If there were any more edges then $2$ edges would connect the same pair of vertices and thus would not be a simple graph.

Is this a known theorem?


1 Answer 1


Yes, it is called the size of a complete graph on $n$ vertices. You can also write it as ${n\choose 2}$ since you have $n$ points and any $2$ of them define an edge.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .