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.

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.

share|improve this question
    
Can you explain more about what exactly you are talking about? I can't tell. –  Mariano Suárez-Alvarez Nov 21 '11 at 16:59
    
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? –  NKLost Nov 21 '11 at 17:02
1  
Explain that in the body of the question, so that people do not have to read through all comments. –  Mariano Suárez-Alvarez Nov 21 '11 at 17:06
    
@NKLost You'll also have to be more clear about how you are connecting the dots. In my mind, connecting 3 dots yields three lines, and 4 dots yield 6 lines. I also see ways in which 234987 dots yield one line. –  process91 Nov 21 '11 at 17:11
1  
@NKLost That said, once you sufficiently rigorize the question, induction will work. –  process91 Nov 21 '11 at 17:17

3 Answers 3

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.