  Suppose a finite, unweighted, combinatorial graph $G = (V,E)$ is the union of
several (degree-)regular graphs which are then additionally connected with a
few additional edges. $G$ will then have only a small number of vertices $v \in
V$ with the property that one of their neighbors $(v,w) \in E$ has a higher
degree $\mbox{deg}(w) > \mbox{deg}(v)$. We prove the converse statement: if a
graph has few vertices having a neighbor with higher degree and satisfies a
mild regularity condition, then, via adding and removing a few edges, the graph
can be turned into a disjoint union of (distance-)regular graphs. The number of
edge operations depends on the maximum degree and number of vertices with a
higher degree neighbor but is independent of the size of $|V|$.
