Xuong tree

In graph theory, a Xuong tree is a spanning tree formula_1 of a given graph formula_2 with the property that, in the remaining graph formula_3, the number of connected components with an odd number of edges is as small as possible.
They are named after Nguyen Huy Xuong, who used them to characterize the cellular embeddings of a given graph having the largest possible genus.
According to Xuong's results, if formula_1 is a Xuong tree
and the numbers of edges in the components of formula_3 are formula_6, then the maximum genus of an embedding of formula_2 is formula_8.
Any one of these components, having formula_9 edges, can be partitioned into formula_10 edge-disjoint two-edge paths, with possibly one additional left-over edge.
An embedding of maximum genus may be obtained from a planar embedding of the Xuong tree by adding each two-edge path to the embedding in such a way that it increases the genus by one.
A Xuong tree, and a maximum-genus embedding derived from it, may be found in any graph in polynomial time, by a transformation to a more general computational problem on matroids, the matroid parity problem for linear matroids.