Definiție
Numim arbore un graf neorientat conex si fără cicluri.![](images/graf.png)
Proprietăți ale arborilor
Teorema 1
Fie G=(V,U) un graf neorientat. Următoarele afirmații sunt echivalente:- G este arbore
- Oricare două vârfuri din G sunt unite printr-un lanț simplu unic
- G este conex minimal (dacă suprimăm o muchie, graful obținut este neconex)
- G este conex si are |V|-1 muchii
- G este aciclic si are |V|-1 muchii
- G este aciclic maximal (dacă adăugăm o muchie, graful obținut conține cicluri)