Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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 ?




share|improve this question

closed as off topic by Doc Brown, Bart van Ingen Schenau, BЈовић, MichaelT, TMN May 3 '13 at 14:20

Questions on Programmers Stack Exchange are expected to relate to software development within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

This looks like a question for math.stackexchange.com –  Bart van Ingen Schenau May 3 '13 at 8:38
add comment

3 Answers

up vote 5 down vote accepted

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.

share|improve this answer
add comment

Consider any minimum spanning tree. Choose some vertex as the root. Then each vertex has one parent, except the root.

share|improve this answer
add comment

Essentially the same as Mason and Mike have already said, but in different words...

If you have no edges, the most (connected) vertices you can have is one. Call this vertex the root.

To add a new vertex to a tree, you must also add a new edge (in order that the new vertex is connected). That edge can (and must) connect to any pre-existing vertex. The new vertex is a child of the pre-existing vertex, and we don't limit the number of children a parent can have.

If you start with just the root (1 vertex and 0 edges) you end up with 2 vertices and 1 edge. Repeat n times to get n+1 vertices and n edges.

This isn't a full proof in itself, but it's impossible to add edges or vertices in any other way (except that you could add two children at once, provided that you do it in a way that's equivalent to doing adding one first then the other). You can't add an edge without adding a vertex because doing so would complete a cycle. You can't add a vertex without adding an edge because that vertex wouldn't be connected to the tree.

BTW - for undirected graphs, words like "root", "parent" and "child" don't mean much, at least not formally. Any vertex in any undirected tree can be considered the root, and which vertex you happen to call the root decides for all edges which vertex is the parent and which is the child. My mental image of a tree tends to include identifying a particular vertex as the root, but that's arguably a misleading mental image.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.