Odd vertex pairing

Let G=(V,E) be an undirected graph. An odd vertex pairing of G is a new graph whose node set is the set of odd degree nodes of G, and in which every node has degree 1.

For a node set $$\emptyset \neq X \subsetneq V$$ , let $$R_G(X)=\max\{\lambda_G(u,v):\ u \in X, v\notin X\},$$ where $$\lambda_G(u,v)$$ is the local edge-connectivity between u and v.

An odd vertex pairing M of G is feasible if $$\frac{d_G(X)-d_M(X)}{2} \geq \left\lfloor\frac{R_G(X)}{2}\right\rfloor$$ for every $$\emptyset \neq X \subsetneq V$$ .

The existence of a feasible odd vertex pairing for any graph G was proved by Nash-Williams , see Nash-Williams' strong orientation theorem. Gabow developed an efficient algorithm to find one. Further properties of odd vertex pairings have been investigated by Király and Szigeti .