# Thread: Graph containing n nodes where n is an integer greater than 1.

1. ## Graph containing n nodes where n is an integer greater than 1.

Hi

The following questions i need help on:
1) Consider a graph containing n cities (nodes), where n is an integer greater than 1.
a) Give a formula for the number of links (lines in the complete graph.
b) Give a formula for the number of links (lines) in the minimal spanning tree.

P.S

2. (a) Hint: If you draw an edge (link) from each node (n choices) to every other node (n - 1 choices), then you will draw every edge in the complete graph twice.

(b) Any tree with n nodes has n - 1 edges. By the way, it does not make sense to talk about a "minimal spanning tree" unless the graph has weights (or distances) assigned to edges. This is because any tree is minimal by definition: it ceases to be connected when any edge is removed. A spanning tree can be defined as a minimal set of edges that connect all vertices in a graph.

3. The number of links (edges)

Example 10 nodes -

1 9 Node 1 links to 9 nodes (and not to its self)
2 8 Node 2 is already linked to bode 1 - so it links to 8 more.
3 7 Node 3 is already linked to 1 and 2 - so it links to 7 more

This continues
4 6
5 5
6 4
7 3
8 2
9 1

So with n nodes - a fully connected graph will have (n^2 - n) / 2 edges.

4. thanks for the help