case depends crucially on the following fact (see figure figure an illustration of the crucial fact about minimum spanning trees proposition let be weighted connected graphand let and be partition of the vertices of into two disjoint nonempty sets furthermorelete be an edge in with minimum weight from among those with one endpoint in and the other in there is minimum spanning tree that has as one of its edges justificationlet be minimum spanning tree of if does not contain edge ethe addition of to must create cycle thereforethere is some edge of this cycle that has one endpoint in and the other in moreoverby the choice of ew( < (fif we remove from }we obtain spanning tree whose total weight is no more than before since was minimum spanning treethis new tree must also be minimum spanning tree in factif the weights in are distinctthen the minimum spanning tree is uniquewe leave the justification of this less crucial fact as an exercise ( - in additionnote that proposition remains valid even if the graph contains negative-weight edges or negative-weight cyclesunlike the algorithms we presented for shortest paths