# Tree (graph theory)

## Undirected, connected and acyclic graph / From Wikipedia, the free encyclopedia

#### Dear Wikiwand AI, let's keep it short by simply answering these key questions:

Can you list the top facts and stats about Tree (graph)?

Summarize this article for a 10 years old

In graph theory, a **tree** is an undirected graph in which any two vertices are connected by *exactly one* path, or equivalently a connected acyclic undirected graph.[1] A forest is an undirected graph in which any two vertices are connected by *at most one* path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees.[2]

**Quick facts: Trees, Vertices, Edges, Chromatic number...**▼

Trees | |
---|---|

Vertices | v |

Edges | v − 1 |

Chromatic number | 2 if v > 1 |

Table of graphs and parameters |

A polytree[3] (or directed tree[4] or oriented tree[5][6] or singly connected network[7]) is a directed acyclic graph (DAG) whose underlying undirected graph is a tree. A polyforest (or directed forest or oriented forest) is a directed acyclic graph whose underlying undirected graph is a forest.

The various kinds of data structures referred to as trees in computer science have underlying graphs that are trees in graph theory, although such data structures are generally rooted trees. A rooted tree may be directed, called a directed rooted tree,[8][9] either making all its edges point away from the root—in which case it is called an arborescence[4][10] or out-tree[11][12]—or making all its edges point towards the root—in which case it is called an anti-arborescence[13] or in-tree.[11][14] A rooted tree itself has been defined by some authors as a directed graph.[15][16][17] A rooted forest is a disjoint union of rooted trees. A rooted forest may be directed, called a directed rooted forest, either making all its edges point away from the root in each rooted tree—in which case it is called a branching or out-forest—or making all its edges point towards the root in each rooted tree—in which case it is called an anti-branching or in-forest.

The term *tree* was coined in 1857 by the British mathematician Arthur Cayley.[18]