Sifat-sifat Pohon (Graf Tree)

· Teorema. Misalkan G = (V, E) adalah graf tak-berarah sederhana dan jumlah simpulnya n. Maka, semua pernyataan di bawah ini adalah ekivalen:

1. G adalah pohon.

2. Setiap pasang simpul di dalam G terhubung dengan lintasan tunggal.

3. G terhubung dan memiliki m = n – 1 buah sisi.

4. G tidak mengandung sirkuit dan memiliki m = n – 1 buah sisi.

5. G tidak mengandung sirkuit dan penambahan satu sisi pada graf akan membuat hanya satu sirkuit.

6. G terhubung dan semua sisinya adalah jembatan.

· Teorema di atas dapat dikatakan sebagai definisi lain dari pohon