If G is a weighted graph, a minimal spanning tree is a spanning tree with minimal weight. For example, if a weighted complete graph represents the cost of directly connecting each pair of nodes, a minimal spanning tree determines a connected network with minimum cost.
The "greedy algorithm" finds a minimal spanning tree in n3 time. If a minimal spanning tree does not contain the smallest edge, we can always add this edge, and delete another edge in the resulting cycle, producing a smaller spanning tree. Therefore the first edge in the constructed minimal spanning tree is the smallest edge in the graph.
By connectivity, at least one incident edge (joining the first edge) must be included in the spanning tree. If the smallest incident edge is not part of a minimal spanning tree, we can always add this edge, and delete another edge in the resulting cycle, producing a smaller spanning tree. By induction, we always add the smallest incident edge that does not produce a cycle. After n-1 edges have been selected, we have a minimal spanning tree.