How to prove max number of connection between n nodes is n*(n-1)/2
algorithm, discrete-mathematics, graph, graph-algorithm
Solution
And one more solution, combinatorial: The problem is equivalent to the number of possible pairs of nodes in the graph, i.e.:
Problem
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.