---
tag: 0MJ0JS72DZ
kind: definition
name: Tree
msc: [05C05]
defines: 062D9KXJB1
uses: [0FFAYNMAJZ, 0XNN9Z8E5A]
sources:
  - url: https://en.wikipedia.org/wiki/Tree_(graph_theory)
    locator: Tree
---

## Definition

A tree is a [[graph|0JD5C82QMB]] that is [[connected|0FFAYNMAJZ]] and [[acyclic|0XNN9Z8E5A]].

## Remarks

Let $T$ be a finite graph with $n \ge 1$ vertices. Then these conditions are equivalent: $T$ is a tree; $T$ is connected with $n - 1$ edges; $T$ is acyclic with $n - 1$ edges.
A graph is a tree if and only if any two vertices are joined by exactly one path. The node [[unique paths in trees|096B7Q5742]] states this.
The [[path graphs|075WR6W3Y3]] and the stars $K_{1,n}$ are trees.

## Explanations

### L1 human

A tree is a connected graph with no loops.
A family tree and the folders on a computer are pictures of trees.