An algorithm to determine the most vital edges of a communication network is presented in this paper.Since a spanning tree consisting of non-failed edges must exist in order for a success state to occur in the all-terminal problem

the number of such spanning trees is a measure of reliability.For a given edge e in the graph G

G*e is the graph with the edge contracted

where the edge denotes a link and the vertex denotes a node respectively.The relative importance of the two edges in the graph can be compared by computing the number of spanning trees of G*e for each of the two edges.The most vital edge in G is an edge whose contraction maximizes the number of spanning trees and whose proper functioning contributes most to system reliability.Experimental results and theoretical analysis show that the edge-contraction algorithm is effective and feasible.