Given n nodes, if every node is connected to every other node (except itself) the number of connections will be n*(n-1)/2
How does one prove this ?
This is not a homework question. I have been away from CS text books for long and have forgotten the theory on how to prove this.
you have n - nodes, each have n -1 connections (each is connected to every node except itself), so we get n*(n-1). However, because connection (x,y) and (y,x) is the same (for all connections), we end up with n*(n-1)/2.
And one more solution, combinatorial: The problem is equivalent to the number of possible pairs of nodes in the graph, i.e.:
Sorry for the bad nomenclature, I'm a physicists, not a CS/Math guy.
Every single node (of which there are n) has to be connected to every one else. There are (n-1) "every one else".
So each n nodes have n-1 connections coming out of them. n(n-1)
But since each connection is "bidirectional" (a to b = b to a), you end up with a factor of 1/2
so n*(n-1)/2
Late and not a proof, but you could "visualize" the nodes as coordinates and relationships as cells in a matrix I don't know how to draw something here.
One column per node, one line per node, the cell at the cross is the relation.
You have xx possible cells. But you need to remove the topleft-bottomright diagonal cells (a node can node be linked to itself). Thus, you remove x cells and have only (xx-x) = x*(x-1) remaining cells. Then, the cell (x,y) is the same link as the cell (y,x), thus you can remove half of the remaining cells : x*(x-1)/2
The degree of each vertex is n-1 (because it has n-1 neighbors).
Handshaking lemma, says: Sigma(deg(v)) (for each node) = 2|E|. Thus:
Sigma(deg(v)) (for each node) = 2|E|
Sigma(n-1) (for each node) = 2|E|
(n-1)*n = 2|E|
|E| = (n-1)*n /2
QED
Proof by induction. Base case - for 2 nodes there is 1 connection and 2 * 1 / 2 == 1. Now assuming that for N nodes we have N * (N-1) / 2 connections. Adding one more node has to establish N additional connections, and:
N * (N-1) / 2 + N =
(N^2 - N + 2N) / 2 =
(N^2 + N) / 2 =
(N + 1) * N / 2
This last line is exactly N * (N - 1) / 2 with N replaced with N+1, so the proof is good.
for 1 node: n connection
for 2 node: n-1 connections(already first node connected )
for 3 node: n-2 connections .. for n node: n-(n-1) connections
Therefore total connections = n + n-1 + n-2 + ........1
= n(n-1)/2 (sum of first n-1 natural numbers)
Another possible equation but not as clean as the suggestions above ((n/2) - 0.5) * n
This question assumes that connections are bidirectional. When discussing Application Integrations or number of integrations between multiple systems, you should not divide by 2! So, if you assume that each connection is unidirectional and that all systems need to talk to each other, the number of integrations between n applications = n*(n-1) This is why point-to-point integrations are discouraged in many real life scenarios.
The most appropriate answer to determine the maximum number of links possible from N network nodes is...
The total number of possible combinations/connections where a link requires 2 nodes; so:
(N!) / [(N-2)!)(2!)] = N(N-1)(N-2)! / (N-2)!(2!);
S
o N(N-1) / 2
where N>1 as it takes 2 nodes to have a Link.
