• ..



Pohon (Tree) didefinisikan sebagai graph terhubung yang tidak mengandung sirkuit. Sedangkan Hutan (Forest) adalah graph yang tidak mengandung sirkuit. Jadi pohon adalah hutan yang terhubung.

Untuk itu perlu diingat kembali bahwa :
• Suatu Graf G disebut terhubung apabila untuk setiap dua simpul dari graf G selalu terdapat jalur yang menghubungkan kedua simpul tersebut.
• Sirkuit atau cycle adalah suatu lintasan tertutup dengan derajat setiap simpul dua.


 
Sifat :
Suatu Graf G adalah Pohon jika dan hanya jika terdapat satu dan hanya satu jalur diantara setiap pasang simpul dari Graf G.
Teorema :
Suatu Graf G dengan n buah simpul adalah Pohon jika :
(1) G terhubung dan tak mengandung sirkuit, atau
(2) G tidak mengandung sirkuit dan mempunyai n - 1 buah ruas, atau
(3) G mempunyai n - 1 buah ruas dan terhubung

Teorema :
Pohon (dan hutan) adalah berwarna 2.