Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to prove max number of connection between n nodes is n*(n-1)/2

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.

like image 538
Manohar Avatar asked Dec 05 '12 19:12

Manohar


People also ask

How do I find out how many network connections I have?

In a network with n users, each user is connected to (n – 1) others, implying a total of n • (n – 1) = n2 – n connections. Since each of these are counted twice, though, the number of unique connections is (n2 – n) ÷ 2 = 0.5n2 – 0.5n.

How many links are there between N nodes?

For all nodes to be linked to every other nodes n(n-1)/2 links are necessary for a non-planar graph. Given a number of nodes, it is possible to find the number of possible combinations: 2n(n-1)/2.

How many connections in a fully connected network?

The number of connections in a full mesh network of n nodes is = n(n - 1) / 2.


1 Answers

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.

like image 154
Aram Gevorgyan Avatar answered Oct 05 '22 23:10

Aram Gevorgyan