Tree graph theory: Encyclopedia II - Tree graph theory - Definitions

Tree graph theory - Definitions

A tree is an undirected simple graph G that satisfies any of the following equivalent conditions:

• 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.
• G is connected and the 3-vertex complete graph K₃ is not a minor of G.
• Any two vertices in G can be connected by a unique simple path.

If G has finitely many vertices, say n of them, then the above statements are also equivalent to any of the following conditions:

• G is connected and has n − 1 edges.
• G has no simple cycles and has n − 1 edges.

An undirected simple graph G is called a forest if it has no simple cycles.

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.

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. 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.

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}.

Adapted from the Wikipedia article "Definitions", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki