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

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