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

• Oct 23rd 2010, 03:21 PM
Paymemoney
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
• Oct 24th 2010, 02:02 AM
emakarov
(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.
• Oct 24th 2010, 02:15 AM
brennan

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