---
tag: KR62B531VT
kind: concept
name: Xuong tree
sources:
  - wikipedia: en:56061994@r1329719589
    locator: Xuong tree
    note: adopted
    mention: wikipedia://en/56061994
    sections: [Summary]
same_as:
  wikidata: Q48999784
  wikipedia: Xuong tree
inventory: [C1YNEYM1XP]
---

## Summary

In graph theory, a **Xuong tree** is a [[spanning tree|0FQ5B8S1ZC]] $T$ of a given graph $G$ with the property that, in the remaining graph $G-T$, 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.