Many networks arise in a random and distributed fashion, and yet result in having a specific type of degree structure: e.g., the WWW, many social networks, biological networks, etc., exhibit power-law, stretched exponential, or similar degree structures. Much work has examined how a graph's degree-structure influences other graph properties such as connectivity, diameter, etc. Probabilistic edge removal models link failures, information spreading, and processes that consider (random) subgraphs. They also model spreading influence of information as in the independent cascade model. We examine what happens to a graph's degree structure under edge failures where the edges are removed independently with identical probabilities. We start by analyzing the effect of edge failure on the degree sequence for power-law and exponential networks, and improve upon results of Martin, Carr & Faulon and Cooper & Lu; then, using intuition from the power-law case, we derive asymptotic results for almost any degree sequence of interest. Our major result shows a classification of degree sequences which leads to simple rules that give much of the new expected degree sequence after random edge-removal; we also provide associated concentration bounds.