Editing Tree (graph theory) (section)

==Properties==
* Every tree is a [[bipartite graph]]. A graph is bipartite if and only if it contains no cycles of odd length. Since a tree contains no cycles at all, it is bipartite.
* Every tree with only [[Countable set|countably]] many vertices is a [[planar graph]].
* Every connected graph ''G'' admits a [[spanning tree (mathematics)|spanning tree]], which is a tree that contains every vertex of ''G'' and whose edges are edges of ''G''. More specific types spanning trees, existing in every connected finite graph, include [[depth-first search]] trees and [[breadth-first search]] trees. Generalizing the existence of depth-first-search trees, every connected graph with only [[Countable set|countably]] many vertices has a [[Trémaux tree]].{{sfnp|Diestel|2005|loc=Prop. 8.2.4}} However, some [[Uncountable set|uncountable]]-[[Order of a graph|order]] graphs do not have such a tree.{{sfnp|Diestel|2005|loc=Prop. 8.5.2}}
* Every finite tree with ''n'' vertices, with {{nowrap|''n'' > 1}}, has at least two terminal vertices (leaves). This minimal number of leaves is characteristic of [[path graph]]s; the maximal number, {{nowrap|''n'' − 1}}, is attained only by [[star graph]]s. The number of leaves is at least the maximum vertex degree.
* For any three vertices in a tree, the three paths between them have exactly one vertex in common. More generally, a vertex in a graph that belongs to three shortest paths among three vertices is called a median of these vertices. Because every three vertices in a tree have a unique median, every tree is a [[median graph]].
* Every tree has a [[graph center|center]] consisting of one vertex or two adjacent vertices. The center is the middle vertex or middle two vertices in every longest path. Similarly, every ''n''-vertex tree has a centroid consisting of one vertex or two adjacent vertices. In the first case removal of the vertex splits the tree into subtrees of fewer than ''n''/2 vertices. In the second case, removal of the edge between the two centroidal vertices splits the tree into two subtrees of exactly ''n''/2 vertices.
* The maximal cliques of a tree are precisely its edges, implying that the class of trees has [[Graphs with few cliques|few cliques]].