First, let's consider this proposition: removing any edge from a tree will create two trees with no connection between them. Let's assume the opposite. We have a graph with two vertices A and B and an edge X between them. Let's assume that even if we remove X, the tree still remains connected. This means a path P exists between A and B even if you delete X. This means in the original graph, we can walk from A to B through P and use X to come back to A. This means the original graph has a cycle. But the original graph was assumed to be a tree, so this is impossible. Therefore, my original proposition that removing any edge from the tree will create two trees with no connection between them is true.

Now let's start with a graph G that has a set of edges E and vertices V. If we remove all the edges, we would of course be left with only V. These set of vertices without edges are actually single vertex trees with no connections between themselves.

We start with one tree, say G, and remove one edge. Now we have two trees. We can now remove another edge, and this will split one of these trees into two so we have three trees. This way, after the removal of each edge, we will have one more tree. Therefore, after the removal of all the edges, we will have |E| + 1 trees (because there was one tree before any edge was removed). These must be |V| single vertex trees. So, it is either |V| = |E|+1 or |E| = |V| - 1.

Let's take an undirected graph. If there are loops and cycles. First, we simply delete all the loops. Consider A and B as two vertices that are neighbors and part of a cycle. This means if we walk through the edge from A to B, we can use another path: B to A (this is what makes it a cycle). So if we delete the B to A edge, we will still have a connected graph. We do this operation for every cycle. At the end of these operations, we will have a connected graph with no loops or cycles; this is a tree. This tree connects all the vertices, so it is a spanning tree.

Now let's check the reverse of the preceding theorem. Suppose there is a connected graph where |V| = |E| + 1. We assume it is not a tree. This graph must have a spanning tree, which is a subgraph, with fewer edges. This spanning tree will have the same number of vertices (because we never deleted any vertices) but fewer edges. Therefore, if the spanning tree has the set of edges E ¹, we have | E ¹|| < |E| => | E ¹|| + 1 < |E| + 1 => | E ¹|| + 1 < |V|. But this is not possible because the new graph is a tree. So the original proposition that any undirected connected graph with the property |V| = |E| +1 is a tree.

Cut refers to a minimum set of edges that when removed would split a connected undirected graph into two separate connected graphs with no connections between them. There can be many cuts in a given graph.

The cut property can be defined as this: if an edge is an element of a cut and has a minimum cost associated with it within the cut, it is part of the minimum spanning tree of the graph. To check this out, first note that for any cut of an undirected connected graph, a spanning tree will always have exactly one member of the cut in it.

Let's have a cut X that divides the graph G into subgraphs H and J. Let G have a spanning tree called S. Since G is a connected graph and X is a cut, this means H and J are connected with each other. If X is empty, it means G was not connected; this is not possible. Now we have the Y subset of X where all the members of Y are part of the spanning tree S. If Y is empty, the vertices of H and J will be disconnected in S, so this is impossible. Now as a contradiction to |Y| = 1, let's assume |Y| > 1. This means there is more than one edge in S, between H and J. Let's pick two of them. Let the first is between vertex A in H and vertex B in J, and the second one between vertex C in H and vertex D in J. Now since the spanning tree S has all the vertices of H and J connected, there is a path from A to C and D to B in S outside of Y. So we have a cycle from A to C and C to D using one of our selected edges and we have D to B and B to A using the other selected edge. This means S has a cycle and hence S is not a tree, which is a contradiction. Therefore, |Y| = 1. Thus, the spanning tree has exactly one member of any cut in an undirected connected graph.

If S is the minimum spanning tree of G and X is a cut in G dividing G into H and J, S has exactly one member for X, as proved in the preceding section. Let it be any edge other than the one with minimum cost. Since S is a spanning tree, if we remove the edge that is in X, we will have two disconnected subtrees, which are spanning trees of H and J. If we insert any other edge from X now, this new edge will connect these subtrees back to the single spanning tree. This is because all the edges of X are between one vertex in H and another in J. So we can replace the edge in S that is a member of X along with the edge in X with minimum cost, and we can thus create another spanning tree of G. But the edges of the new tree will be the same as in S, except the one that has a lesser cost than the one in S. So the sum of the costs of edges of the new spanning tree must be lesser than that of S, which is a contradiction as S is a minimum spanning tree. Therefore, the minimum spanning tree S must have an edge with the least cost within the cut X.

Let's assume that we have a connected undirected graph G for which there are two different minimum spanning trees, namely S and T. Since S and T are different and have the same number of edges (because for a spanning tree, the calculation is |V| = |E| + 1), there is an edge E in S that is not in T. Let this edge be there between the vertices A and B. Now let's create a partition of the set of vertices in G so that there are two partitions: Y and Z. Create this such that A belongs to Y, B belongs to Z, and Y and Z are disjointed and together contain all the vertices. Let X be the cut that would divide G into two subgraphs with vertices in Y and Z. Since A belongs to Y and B belongs to Z, the edge E between A and B belongs to X. Since X is a cut and S is a spanning tree, there must be exactly one edge in X that is part of S; in this case, it has to be the edge E. Now, since T is also a spanning tree and E is not a member of T, there must be another member of X that is in T; let it be f.

If we remove the edge E from S, we will have two different trees, which would be joined again if we insert f. This is because f is an edge between the vertices in Y and Z, and the two parts are already trees. So now we are left with another spanning tree.

All the costs are different; the cost of E is different from the cost of f. If the cost of f is lower than that of E, the total cost of the new spanning tree is lower than that of S. Although, this is not possible because S is a minimum spanning tree. So, the cost of f is higher than that of E.

We can do this for every edge in S that is not in T; S will transform into T when no more edges are available. In every step of this process, the total cost of edges will increase. This means the total cost of edges in T must be higher than that in S. However, this is impossible because S and T are both minimum spanning trees. So our original assumption that there can be two different minimum spanning trees is wrong. Therefore, each minimum spanning tree is unique in a graph where all the costs of the edges are different.