**tree**is a graph in which any two vertices are connected by

*exactly one*path. A

**forest**is a graph in which any two vertices are connected by

*at most one*path. An equivalent definition is that a forest is a disjoint union of trees (hence the name).

Table of contents |

2 Example 3 Facts 4 Types of Trees |

## Definitions

*G*is connected and has no simple cycles*G*has no simple cycles and, if any edge is added to*G*, then a simple cycle is formed*G*is connected and, if any edge is removed from*G*, then it is not connected anymore- Any two vertices in
*G*can be connected by a unique simple path.

*G*has finitely many vertices, say

*n*of them, then the above statements are also equivalent to:

*G*is connected and has*n*-1 edges*G*has no simple cycles and has*n*-1 edges

*G*is called a

*forest*if it has no simple cycles.

## Example

## Facts

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*^{n-2} 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

## Types of Trees

- Free tree
- Rooted tree
- Ordered tree

- Binary tree
- Positional tree
- Empty tree
- K-ary tree
- Charles' tree