I'm not so hot on the maths for this but for what I understand...A graph g exists with v vertices and edges. g = (V,E);The spanning graph for this is an acyclic copy of this where all the vertices are present, and all the edges are a subset of the graph with the condition that each connection is distinct.Apparently the MST should have n-1 nodes. How can this be proven ? Sources:http://youtu.be/zFbq8vOZ_0k?t=25m1shttp://www.gtkesh.com/minimum-spanning-tree/
How can you prove an acyclic graph has n-1 edges?
algorithms;graph;trees
Proof by induction:Every acyclic graph can be represented as a tree, if all the nodes are connected.So let's think about trees.  You've got one root node.  Let's look at the simplest, case, in which the tree only has one branch, and so it's a simple linked list.If there are two nodes, there's one edge between them.  Add one node to the end of the linked list, and there are three nodes and two edges, and so on.Now if we take the linked list and add another node to one of the nodes in the middle, we have a true tree.  And again, we're adding one node along with one edge.  Add another one, and it's the same.No matter how many nodes you add, or where you add them, as long as it remains an acyclic, fully connected tree, there will always be N-1 edges for N nodes.