Definition:Tree (Graph Theory)

From ProofWiki
Jump to: navigation, search

This page is about trees in the context of graph theory. For other uses, see Definition:Tree.

Definition

Definition 1

A tree is a simple connected graph with no circuits.


Definition 2

A tree is a simple connected graph with no cycles.


Node

The vertices of a tree are called its nodes.


Leaf Node

Let $v$ be a node of a tree $T$.

Then $v$ is a leaf node of a $T$ if and only if $v$ is of degree $1$.


If $T$ is a rooted tree, this is equivalent to saying that $v$ has no child nodes.


Finite or Infinite

Finite Tree

A tree is finite if and only if it contains a finite number of nodes.


Infinite Tree

A tree is infinite if it contains a (countably) infinite number of nodes.


Also defined as

In some contexts, the term tree is used to mean rooted tree.


Also see

  • Results about trees can be found here.