Editing Tree (graph theory) (section)

===Tree===
A ''tree'' is an undirected graph {{mvar|G}} that satisfies any of the following equivalent conditions:
* {{mvar|G}} is [[Connected graph|connected]] and [[Cycle (graph theory)|acyclic]] (contains no cycles).
* {{mvar|G}} is acyclic, and a simple cycle is formed if any [[Edge (graph theory)|edge]] is added to {{mvar|G}}.
* {{mvar|G}} is connected, but would become [[Connectivity (graph theory)#Connected graph|disconnected]] if any single edge is removed from {{mvar|G}}.
* {{mvar|G}} is connected and the [[complete graph]] {{math|''K''{{sub|3}}}} is not a [[Minor (graph theory)|minor]] of {{mvar|G}}.
* Any two vertices in {{mvar|G}} can be connected by a unique [[Path (graph theory)|simple path]].
If {{mvar|G}} has finitely many vertices, say {{mvar|n}} of them, then the above statements are also equivalent to any of the following conditions:
* {{mvar|G}} is connected and has {{math|''n'' − 1}} edges.
* {{mvar|G}} is connected, and every [[subgraph (graph theory)|subgraph]] of {{mvar|G}} includes at least one vertex with zero or one incident edges. (That is, {{mvar|G}} is connected and [[Degeneracy (graph theory)|1-degenerate]].)
* {{mvar|G}} has no simple cycles and has {{math|''n'' − 1}} edges.
As elsewhere in graph theory, the [[order-zero graph]] (graph with no vertices) is generally not considered to be a tree: while it is vacuously connected as a graph (any two vertices can be connected by a path), it is not [[n-connected|0-connected]] (or even (−1)-connected) in algebraic topology, unlike non-empty trees, and violates the "one more vertex than edges" relation. It may, however, be considered as a forest consisting of zero trees.

An {{em|internal vertex}} (or inner vertex) is a vertex of [[Degree (graph theory)|degree]] at least 2. Similarly, an {{em|external vertex}} (or outer vertex, terminal vertex or leaf) is a vertex of degree 1. A branch vertex in a tree is a vertex of degree at least 3.<ref>{{cite arXiv |last1=DeBiasio |first1=Louis |last2=Lo |first2=Allan |date=2019-10-09 |title=Spanning trees with few branch vertices |class=math.CO |eprint=1709.04937 }}</ref>

An {{em|irreducible tree}} (or series-reduced tree) is a tree in which there is no vertex of degree 2 (enumerated at sequence {{OEIS link|A000014}} in the [[OEIS]]).{{sfn|Harary|Prins|1959|p=150}}