Problem formulations are presented for the evaluation of upper and lower bounds on the effect of progressive structural degradation. For the purposes of this study, degradation effect is measured by an increase in global structural compliance (flexibility). Thus the stated bounds are given simply by the maximum and minimum values, respectively, of the increase in compliance corresponding to a specified global interval of degradation. Solutions to these optimization problems identify the particular patterns of local degradation associated with the respective 'worst case' and 'least degrading' interpretations. Several formulations for extremal 'loss of stiffness', each with one or another form of model for local degradation, are compared and evaluated. An isoperimetric constraint controls the degree of loss in overall structural stiffness. Results obtained sequentially for a set of specified, increasing values for the bound in this constraint track the evolution of local degradation. While the full exposition of the paper is written specifically for trussed structures, analogues for the more useful formulations are described as well for the treatment of continuum systems. Implementation of methods for computational solution are described in detail, and computational results are given for the bound solutions corresponding to evolution from a starting structure through to its fully degraded form.