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

algorithm graph graph-algorithm discrete-mathematics
Manohar picture Manohar · Dec 5, 2012 · Viewed 24.5k times · Source

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.

Answer

Aram Gevorgyan picture Aram Gevorgyan · Dec 5, 2012

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.

Related questions

Explanation of Algorithm for finding articulation points or cut vertices of a graph

I have searched the net and could not find any explanation of a DFS algorithm for finding all articulation vertices of a graph. There is not even a wiki page. From reading around, I got to know the basic facts …

Read More
How to find if a graph is bipartite?

I have been trying to understand the bipartite graph. To my understanding it is a graph G which can be divided into two subgraphs U and V.So that intersection of U and V is a null set and union …

Read More
Algorithm for diameter of graph?

If you have a graph, and need to find the diameter of it (which is the maximum distance between two nodes), how can you do it in O(log v * (v + e)) complexity. Wikipedia says you can do this using …

Read More