Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
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
add comment

4 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
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
add comment

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,

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.