A tree, in graph theory, is a connected, undirected Graph that contains no closed loops. A forest is a disconnected graph whose connected parts are trees.

A tree in graph theory is a particular kind of Tree (combinatorial structure).

Trees are often drawn in a "rooted" manner. However, topologically, no node is distinguished as a root, and we could choose any node to be the root in this representation.

Properties

• There is exactly one path between every two points. If there were two one could use them to make a loop.
• A tree of $n$ vertices always exactly $n-1$ edges (seen by constructing the tree in rooted form).
• A connected network with $n$ vertices with the minimum number of edges is always a tree (See Newman pages 128-129 for proofs).

Applications

Computer Science

• Data structures
  • AVL trees
  • Heaps
• Minimum spanning trees
• Cayley trees
• Bethe latices
• Hierarchical models of networks

Network theory

• small components in the network of a Random Graph are trees
• Dendograms, a hierarchical decomposition of a network as a tree.

Physics

• Feynman diagrams