I am trying to find the relation between the number of nodes and the number of connections possible. So if there are $0$ nodes, that means $0$ connections possible, $1$ node still means $0$ connections possible, $2$ nodes $1$ connection possible, $3$ nodes $3$ connection and so on. How can I find the relation between $n$ nodes and the number of possible connections ?
$\endgroup$ 44 Answers
$\begingroup$the sequence is $a_0,a_1,a_2\dots$ with $a_n=\frac{n(n-1)}{2}$
$\endgroup$ 1 $\begingroup$Let $a_n$ be the number of connections for $n$ nodes.
For $n > 0$, we have $a_n = a_{n-1} + n-1$ because among the $a_n$ connections, there are $n-1$ of them that connect to the $n^{th}$ node while $a_{n-1}$ of them didn't.
Rewrite above expression as $a_k - a_{k-1} = k-1$. Start summing both sides from $k = 1$ to $n$, we get
$$a_n - a_0 = \sum_{k=1}^n (k-1) = \sum_{k=1}^n \frac{k(k-1)-(k-1)(k-2)}{2} = \frac{n(n-1)}{2}$$
Together with $a_0 = 0$, we find $a_n = \frac{n(n-1)}{2}$ for $n > 0$.
Since this is trivially true at $n = 0$, we have $a_n = \frac{n(n-1)}{2}$ in general.
Hint: If you have graph on $n$ nodes, an edge in the graph corresponds to a choice of $2$ of these nodes (the $2$ which the edge connects). Hence the number of possible edges in the graph is the number of ways you can choose $2$ nodes. Can you continue from here?
$\endgroup$ 3 $\begingroup$$a_n - a_{n-1} = n-2 \implies a_n = n-2 + n-3 +....+1 = ...$
$\endgroup$
