When bad things happen to good trees

When the edges in a tree or rooted tree fail with a certain fixed probabili ty, the (greedoid) rank may drop. We compute the expected rank as a polynom ial in p and as a real number under the assumption of uniform distribution. We obtain several different expressions for this expected rank polynomial for both trees and rooted trees, one of which is especially simple in each case. We also prove two extremal theorems that determine both the largest a nd smallest values for the expected rank of a (rooted or unrooted) tree, an d precisely when these extreme bounds are achieved. We conclude with direct ions for further study. (C) 2001 John Wiley & Sons, Inc. J Graph Theory 37: 79-99, 2001.