For every vertex choose at least one partner, preferably the one who has no pair yet, and select this edge.

Try to find a path that alternatively contains selected and unselected edges, such that it starts and ends on the same side and each end of the path belongs to at least two selected edges. Flip selected/unselected segments on the path thus reducing the number of selected edges by one.

Btw, to avoid any code duplication one may represent the graph as a four-dimensional array: [which delegation][selected or unselected][vertex index][index of the partner].