ein zusammenhängender Graph ohne Kreise.

Die Ecken eines Baumes vom Grad 1 sind seine Blätter. Jeder Baum T der Ordnung |E(T)| ≥ 2 besitzt mindestens zwei Blätter – etwa die Endecken eines längsten Weges in T. Dies kann bei Induktionsbeweisen für Bäume nützlich sein, denn entfernt man aus einem Baum ein Blatt, so entsteht wieder ein Baum. Die Zusammenhangskomponenten eines Waldes sind Bäume.

Folgende Charakterisierungen von Bäumen lassen sich recht einfach nachweisen. Ein Graph ist genau dann ein Baum, wenn je zwei verschiedene Ecken durch genau einen Weg verbunden sind. Ein zusammenhängender Graph mit n Ecken ist genau dann ein Baum, wenn er (n − 1) Kanten besitzt.

Auch die nächste Eigenschaft von Bäumen ist leicht einzusehen. Verbindet man zwei verschiedene Ecken eines Baumes durch eine zusätzliche Kante, so entsteht ein Graph mit genau einem Kreis.

Ein zusammenhängender gerichteter GraphD, dessen untergeordneter Multigraph keinen Kreis besitzt, heißt gerichteter Baum.