Graph decomposition via edge edits into a union of regular graphs

Tony Zeng

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$…