Trees  

A labeled tree with 6 vertices and 5 edges 

Vertices  v 
Edges  v  1 
Chromatic number  2 
In mathematics, more specifically graph theory, a tree is a graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree. A forest is a disjoint union of trees.
The various kinds of trees used as data structures in computer science are not really trees in this sense, but rather, types of ordered directed trees; see below.
Contents 
A tree is an undirected simple graph G that satisfies any of the following equivalent conditions:
If G has finitely many vertices, say n of them, then the above statements are also equivalent to any of the following conditions:
An irreducible (or seriesreduced) tree is a tree in which there is no vertex of degree 2.
An undirected simple graph G is called a forest if it has no simple cycles.
The term hedge sometimes refers to an ordered sequence of trees.
A polytree is a directed graph with at most one undirected path between any two vertices. In other words, a polytree is a directed acyclic graph for which there are no undirected cycles either.
A directed tree is a directed graph which would be a tree if the directions on the edges were ignored. Some authors restrict the phrase to the case where the edges are all directed towards a particular vertex, or all directed away from a particular vertex (see arborescence).
A tree is called a rooted tree if one vertex has been designated the root, in which case the edges have a natural orientation, towards or away from the root. The treeorder is the partial ordering on the vertices of a tree with u ≤ v if and only if the unique path from the root to v passes through u. A tree which is a subgraph of some graph G is a normal tree if the ends of every edge in G are comparable in this treeorder (Diestel 2005, p. 15). Rooted trees, often with additional structure such as ordering of the neighbors at each vertex, are a key data structure in computer science; see tree data structure. In a context where trees are supposed to have a root, a tree without any designated root is called a free tree.
In a rooted tree, the parent of a vertex is the vertex connected to it on the path to the root; every vertex except the root has a unique parent. A child of a vertex v is a vertex of which v is the parent. A leaf is a vertex without children.
A labeled tree is a tree in which each vertex is given a unique label. The vertices of a labeled tree on n vertices are typically given the labels 1, 2, …, n. A recursive tree is a labeled rooted tree where the vertex labels respect the tree order (i.e., if u < v for two vertices u and v, then the label of u is smaller than the label of v).
An ordered tree is a rooted tree for which an ordering is specified for the children of each vertex.
An nary tree is a rooted tree for which each vertex which is not a leaf has at most n children. 2ary trees are sometimes called binary trees, while 3ary trees are sometimes called ternary trees.
The example tree shown to the right has 6 vertices and 6 − 1 = 5 edges. The unique simple path connecting the vertices 2 and 6 is 2456.
Given n labeled vertices, there are n^{n−2} different ways to connect them to make a tree. This result is called Cayley's formula. It can be proved by first showing that the number of trees with n vertices of degree d_{1},d_{2},...,d_{ n} is the multinomial coefficient
An alternative proof uses Prüfer sequences. This is the special case for complete graphs of a more general problem, counting the number of spanning trees in an undirected graph, which can be achieved by computing a determinant according to the matrix tree theorem. The similar problem of counting all the subtrees regardless of size has been shown to be #Pcomplete in the general case (Jerrum (1994)).
Counting the number of unlabeled trees is a harder problem. No closed formula for the number t(n) of trees with n vertices up to graph isomorphism is known. Otter (1948) proved that
with C = 0.53495… and α = 2.95576… (here, means that ).
