5
$\begingroup$

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?

  • 0
    Perfect, thanks :)2012-09-30

4 Answers 4

7

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, 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.

  • 0
    @GrowinMan: You’re very welcome.2012-09-30
1

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,

1

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.

0

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