# Given the number of vertices in a graph, does the formula for max number of edges it can have make intutive sense?

I hope I'm able to put the question clearly.

Suppose a pen costs x dollars, and I buy 3 pens. So the formula for total cost is : 3x

This makes sense, since total cost is cost of one pen times number of pens.

For a graph with n vertices, there are at the most 1+2+3....(n-1) edges it can have. Which is basically (n-1)*n/2

How can I make similar intutive sense out of this formula?

-
Don't try to understand the number of possible edges, try to understand the set of possible edges. There's one possible edge for each $2$-element subset of the set of vertices. How many $2$-element subsets of an $n$-element set are there? –  Qiaochu Yuan Sep 30 '12 at 19:46
That really helps. If you were to pick any two elements for an edge from the set of all vertices, first you'd have n choices, and then (n-1) choices. But this would count every edge A-B as B-A again separately too, hence divide by two. Is that right @QiaochuYuan? –  GrowinMan Sep 30 '12 at 19:49
Yes, that's right. –  Qiaochu Yuan Sep 30 '12 at 19:50
Perfect, thanks :) –  GrowinMan Sep 30 '12 at 19:50

Consider the following table. The top row and lefthand column list the $n$ vertices of a graph. The body of the table shows an $X$ or an $O$ for each possible edge. Notice, though that each possible edge is shown twice, once marked $X$ and once marked $O$. Specifically, if $i<k$, the possible edge between $v_i$ and $v_k$ is marked $X$ in row $i$, column $k$, and $O$ in row $k$, column $i$. Thus, to count the number of possible edges, we should count either the $X$’s or the $O$’s, but not both.

$$\begin{array}{r|c|c} &v_1&v_2&v_3&\dots&v_{n-1}&v_n\\ \hline v_1&-&X&X&\dots&X&X\\ \hline v_2&O&-&X&\dots&X&X\\ \hline v_3&O&O&-&\dots&X&X\\ \hline \vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ \hline v_{n-1}&O&O&O&\dots&-&X\\ \hline v_n&O&O&O&\dots&O&- \end{array}$$

As you can see from the arrangement, the number of $X$’s (or $O$’s) is clearly $$1+2+3+\ldots+(n-1)\;.$$ On the other hand, there are $n^2$ cells in the table, of which $n$ are on the diagonal and represent impossible edges, so there are $n^2-n$ $X$’s and $O$’s altogether. We want just the $X$’s (or just the $O$’s), so we want half of that number, which is $$\frac{n^2-n}2=\frac{n(n-1)}2\;.$$ We conclude, then, that the number of possible edges is

$$1+2+3+\ldots+(n-1)=\frac{n(n-1)}2\;.$$

If you know about binomial coefficients, you can see this in another way: each edge corresponds to one possible choice of two of the $n$ vertices, and there are $$\binom{n}2=\frac{n(n-1)}2$$ ways of choosing two from a set of $n$ objects.

-
Brilliant. Thank you for your time in the elaborate explanation. –  GrowinMan Sep 30 '12 at 20:03
@GrowinMan: You’re very welcome. –  Brian M. Scott Sep 30 '12 at 20:08

You can also argue by induction: let us have a graph with $n$ vertices and max. number of edges, then consider an (n+1)th vertex: you can draw $+n$ edges. For one vertex there cannot be edges, and hence it is $0+1+2+\ldots+(n-1)$ for $n$ edges.

By the way, one could also consider graphs with loops or parallel arrows, even directed graphs.. If multiple arrows allowed, then there is no upper limit on their numbers,

-

Note: This problem is intuitively the same as the handshake problem where instead of counting the max handshakes among $n$ people you want to find the max edges among $n$ vertices.

Suppose we have $n$ vertices labeled $v_i$, $(i = 1,...,n)$ (the actual order is irrelevant) :

Step 1) Take vertex $v_1$ and connect it to all other $(n-1)$ vertices, now disgard $v_1$.

Step 2) Take vertex $v_2$ and connect it to all other $(n-2)$ vertices, now disgard $v_2$.

$$...$$

Step n-2) Take $v_{n-2}$ and connect it to all other $(2)$ vertices, now disgard $v_{n-2}$.

Step n-1) Take $v_{n-1}$ and connect it to all other $(1)$ vertices, now disgard $v_{n-1}$.

Now, notice the number of edges (in parenthesis) above we add in each step can be written as:$$\sum\limits_{i=1}^{n-1} i = \frac{n(n-1)}{2}$$

-

Cut each edge in the middle, making two half-edges, one dangling from each endpoint. Now, each vertex can have a maximum of $n-1$ half-edges, one reaching towards each of the other vertices. $n$ vertices, each with $n-1$ half-edges attached to it, makes a total of $n(n-1)$ half-edges, or $\frac{n(n-1)}2$ whole edges.

-