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