Graph Tree

Jump to navigation Jump to search

A Graph Tree is an connected graph that is an acyclic graph (in which any two nodes are connected by exactly one graph path).



  1. In particular, some authors consider that directed rooted trees are not descriptive enough as to the direction of the arcs, for instance
  2. Cayley (1857) "On the theory of the analytical forms called trees," Philosophical Magazine, 4th series, 13 : 172–176.
    However it should be mentioned that in 1847, K.G.C. von Staudt, in his book Geometrie der Lage (Nürnberg, (Germany): Bauer und Raspe, 1847), presented a proof of Euler's polyhedron theorem which relies on trees on pages 20–21. Also in 1847, the German physicist Gustav Kirchhoff investigated electrical circuits and found a relation between the number (n) of wires/resistors (branches), the number (m) of junctions (vertices), and the number (μ) of loops (faces) in the circuit. He proved the relation via an argument relying on trees. See: Kirchhoff, G. R. (1847) "Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird" (On the solution of equations to which one is led by the investigation of the linear distribution of galvanic currents), Annalen der Physik und Chemie, 72 (12) : 497–508.


  • (Weisstein, 2009) ⇒ Eric W. Weisstein. (2009). “Tree.” In: MathWorld -- A Wolfram Web Resource.
    • QUOTE: A tree is a mathematical structure that can be viewed as either a graph or as a data structure. The two views are equivalent, since a tree data structure contains not only a set of elements, but also connections between elements, giving a tree graph.

      Trees were first studied by Cayley (1857). McKay maintains a database of trees up to 18 vertices, and Royle maintains one up to 20 vertices.

      A tree is a set of straight line segments connected at their ends containing no closed loops (cycles). In other words, it is a simple, undirected, connected, acyclic graph (or, equivalently, a connected forest). A tree with n nodes has n-1 graph edges. Conversely, a connected graph with n nodes and n-1 edges is a tree. All trees are bipartite graphs (Skiena 1990, p. 213). Trees with no particular node singled out are sometimes called free trees (or unrooted tree), by way of distinguishing them from rooted trees (Skiena 1990, Knuth 1997).


  • (Cayley, 1891) ⇒ A. Cayley. (1891). “On the Theory of Analytic Forms Called Trees.” Philos. Mag. 13, 19-30, 1857. Reprinted in Mathematical Papers, Vol. 3.