---
tag: 6J20G0YPWH
kind: concept
name: Trémaux tree
aliases: [charles-pierre-tremaux, charles-tremaux, normal-tree]
sources:
  - wikipedia: en:30247317@r1375502672
    locator: Trémaux tree
    note: adopted
    mention: wikipedia://en/30247317
    sections: [Summary]
same_as:
  wikidata: Q7849146
  wikipedia: Trémaux tree
inventory: [M0PTZNPN4J]
---

## Summary

In graph theory, a **Trémaux tree** of an undirected graph $G$ is a type of [[spanning tree|0FQ5B8S1ZC]], generalizing depth-first search trees. They are defined by the property that every edge of $G$ connects an ancestor–descendant pair in the tree. Trémaux trees are named after Charles Pierre Trémaux, a 19th-century French author who used a form of depth-first search as a strategy for solving mazes. They have also been called **normal spanning trees**, especially in the context of infinite graphs.