Transforming paths to black cycles.

<p>Vertices u, v are matched. The upper path is (u, a, b, c, d, e, f, v), and the bottom path is (u, g, h, e, d, i, j, k, v). Four colored subpaths on the left are contracted into four edges in the right cycles, respectively. An odd path is transformed into an even cycle, while an even path is transformed into an odd cycle. Solid and dashed edges correspond to black and gray edges, respectively.