1
$\begingroup$

Short version:

If you take n vertices and connect them together with lines, you'll have nāˆ’1 lines, why nāˆ’1? Other than the obvious visual proof, is there something that could be more, I don't know, substantial?

O - dot

O------------------------O------------------------O Three dots, two lines. $n$ -> $n-1$

Longer version:

Other than the obvious there's three dots, there are two lines - therefore $n-1$ is there some sort of a proof? For example, I can easily see how $n$ disconnected dots give $n/2$ lines, because there must be $m$ groups of 2 dots or $m$ lines.

I've been thinking about this a bit, if there's n dots, only the first line requires two unique dots and every subsequent one requires only 1 additional. But I still don't see the $n-1$ in that. Please assist me with this triviality, thanks!

Dots/vertices, however you want to name them.

  • 0
    Ultimately it doesn't have to be "in a linear fashion" - this generalizes to [finite] trees. (basically, you get to attach the "then line, dot" anywhere instead of at the dot you added most recently) – 2011-11-21

3 Answers 3

4

If you are in $1$ town and you want to visit $n$ towns, then you have to walk to $n-1$ towns.

4

See Fencepost Error. This is really just a matter of counting carefully, and of having a precise understanding of what you are counting.

Here's what I think you mean: You have $n$ vertices $v_1, v_2, v_3, \ldots, v_n$, and you want to count the line segments connecting ($v_1$ and $v_2$), ($v_2$ and $v_3$), $\ldots$, all the way to ($v_{n-1}$ and $v_n$).

We can label each line segment by taking the smaller of the indices of the two vertices $v_i$ and $v_j$ it connects. Then we have $n-1$ line segments, $\ell_1, \ell_2, \ldots, \ell_{n-1}$.

Notice that if we connected the vertices in a loop, we would have one more line segment, connecting ($v_n$ and $v_1$), to make $n$ total line segments. If we have a single chain (not a loop) with $n$ interior vertices, then we have $n+1$ line segments. (That is, we add vertices $v_0$ on one end and $v_{n+1}$ on the other end, making $n+2$ vertices total, but only $n$ interior vertices.)

In counting problems like this, you have to think carefully about the correct way to count.

1

Instead of counting lines, how about counting left ends of lines? Every dot except the last one is adjacent to exactly one left end, and the last one is adjacent to none.

There are $n-1$ dots-except-the-last-one (which is just how subtraction works, nothing to prove there), so that is also the number of left ends, and therefore also the number of lines.