I am trying to determine how they derived number of cables needed in a full mesh network
According to networking books it is $\dfrac{N * (N-1)}{2}$, where N is the number of nodes.
I tried drawing out the problem, but I am really baffled (haven't done these problems since High School!)
So far I have:
$$N + (N-1) + (N-2) + (N-3) + \cdots + (N-N-1)$$
$$= N * (N-1) - (1 + 2 + \cdots + (N-1))$$
$$= N * (N-1) - \dfrac{(N-1) + 1} { 2}$$
$$= N * (N-1) - \dfrac{N}{2}$$
$$= \dfrac{2N^2 -2N -N}{2}$$
I am really stumped, please help!!!!!!!
$\endgroup$ 52 Answers
$\begingroup$Think of it this way. The nodes are like the vertices (end-points) of a polygon. Let's say there are $N$ nodes. You want to be able to connect every node to every other node (with line segments that represent "edges" and "diagonals"), but without redundancy. This is equivalent to drawing line segments from every vertex of the polygon to every other vertex without redundancy (i.e. two vertices are connected by exactly one line segment).
Start with an unconnected graph of the polygon (i.e. just the vertices, no line segments yet). Label the nodes $1$ through $N$ counter-clockwise (the direction doesn't matter, as long as it's consistent). From the first node, you can draw segments connecting to $N-1$ nodes (i.e. every other node).
Now move on to node $2$. It's already connected to node $1$. You need to connect it to $N-2$ remaining nodes.
Similarly, working in this fashion, you should be able to see that the number of line segments "emanating" from each node is as follows:
Node $1$: $N-1$
Node $2$: $N-2$
...
Node $k$: $N-k$
...
Node $N-1$: $1$
Node $N$: $0$
All you need is to sum all those line segments up to find $S_N$.
$S_N = (N-1) + (N-2) + ... + 1$
Now you can use the formula for an arithmetic series here. But there is a simple way to do it from first principles. Write the same sum backwards. The terms are reversed but the sum remains the same:
$S_N = 1 + 2 + ... + (N-1)$
Now sum them term by term:
$2S_N = N + N + ... + N$
$2S_N = (N)(N-1)$
since there are $N-1$ terms in the sequence.
That immediately gives:
$\displaystyle S_N = \frac{N(N-1)}{2}$
as required.
$\endgroup$ 2 $\begingroup$There is a simple combinatorial argument for this: each wire is connected to two nodes, and the order of choosing the nodes does not matter (a wire from $A$ to $B$ is the same as a wire from $B$ to $A$, obviously).
What does this mean? A wire can be labelled by its connections at each end, as a pair $(A,B)$. I can't have $(A,A)$, however, and $(A,B)$ is the same as $(B,A)$. So how many such pairs are there? I start with $N^2$, then exclude $N$ that have the same node in both slots in the pair, then each remaining pair is the same as exactly one other. So in the end I have $$ \frac{1}{2}(N^2-N) = \frac{N(N-1)}{2}. $$
The more concise way to say this is that I have $N$ choices for the first node, $N-1$ for the second, and then the order of choosing does not matter, so only half of the total choices are distinct. Similarly, if I was picking a set of $3$ distinct objects, I have $\frac{N(N-1)(N-2)}{2 \times 3}$ distinct options.
$\endgroup$
