
An undirected simple graph G is called a tree if it satisfies one (and therefore all) of the following equivalent conditions:
The example tree shown to the right has 6 vertices and 61=5 edges. The unique simple path connecting the vertices 2 and 6 is 2456.
Every tree is planar and bipartite.
Every connected graph G admits a spanning tree, which is a tree that contains every vertex of G and whose edges are edges of G.
Given n different vertices, there are n^{n2} different ways to connect them to make a tree. No closed formula for the number t(n) of trees with n vertices up to graph isomorphism is known. However, the asymptotic behavior of t(n) is known: there are numbers α≈3 and β≈0.5 such that
See also Tree structure.
Search Encyclopedia

Featured Article
