Pohon merupakan salah satu graf khusus dengan ciri-ciri tertentu. Menurut catatan sejarah, pohon digunakan pertama kali pada tahun 1857 oleh seorang matematikawan berkebangsaan Inggris bernama Arthur Cayley (1821–1895). Cayley menggunakannya untuk menghitung jenis senyawa kimia tertentu. Sejak saat itu, pohon banyak diaplikasikan untuk menyelesaikan berbagai masalah lintas bidang sampai saat ini.
Graf khusus seperti itu diberi nama “pohon” karena model graf tersebut dapat digambarkan sebagai pohon dengan banyak percabangannya. Selain itu, istilah pohon (yang bukan merujuk pada tumbuhan) juga sebenarnya telah kita gunakan dalam kehidupan sehari-hari, misalnya pohon faktor dan pohon keluarga. Pada pohon keluarga, simpul merepresentasikan anggota keluarga, sedangkan sisi merepresentasikan hubungan orang tua dan anak. Sebagai contoh, berikut ini merupakan contoh pohon keluarga Patrick, salah satu karakter dalam animasi serial SpongeBob SquarePants.
Ketika pertama kali belajar pohon, kita akan bertemu dengan banyak terminologi baru yang berhubungan erat dengan botani, seperti akar, cabang, daun, dan sebagainya. Selain itu, istilah kekeluargaan juga akan ditemukan (mungkin terdengar unik), seperti induk, anak, saudara kandung, keturunan, leluhur, dan sebagainya.
Artikel tentang Graf
Berikut ini merupakan beberapa artikel yang tersedia terkait dengan materi graf.
Materi, Soal, dan Pembahasan – Dasar-Dasar Graf dan Terminologinya
Materi, Soal, dan Pembahasan – Operasi pada Graf dan Konsep Subgraf
Materi, Soal, dan Pembahasan – Representasi Graf dan Isomorfisme Graf
Berikut ini merupakan definisi formal dari pohon.
Definisi: Pohon
Dari definisi tersebut, kita tahu bahwa semua pohon merupakan graf, tetapi tidak semua graf merupakan pohon. Ada syarat khusus agar graf dapat disebut sebagai pohon, yaitu graf tersebut harus terhubung dan tidak memuat siklus. Selain itu, pohon harus berupa graf hingga (finite graph), artinya simpulnya ada sebanyak berhingga. Contoh graf sederhana yang merupakan pohon adalah graf trivial, yaitu graf yang memiliki satu simpul saja tanpa sisi. Graf lengkap dengan dua simpul juga merupakan pohon. Namun, graf lengkap dengan tiga simpul bukan pohon karena memuat siklus. Lebih lanjut, pohon pasti merupakan graf sederhana karena jika tidak, sisi rangkap atau gelang akan membuat graf itu memiliki siklus sehingga bertentangan dengan definisi pohon.
Contoh lain diberikan sebagai berikut.
Graf $K$ bukan pohon karena memuat siklus, salah satunya seperti yang ditandai dengan simpul dan sisi berwarna merah. Graf $L$ merupakan pohon. Dapat dilihat bahwa $L$ tidak memuat siklus. Perhatikan bahwa kita dapat menjadikan graf $K$ sebagai pohon dengan menghapus (menghilangkan) sisi pembentuk siklusnya.
Teorema: Bilangan Kromatik Pohon
Misalkan $T = (V, E)$ merupakan sembarang pohon. Pertama, beri warna pertama pada sembarang simpul $T.$ Kemudian, beri warna kedua pada simpul-simpul yang bertetangga dengannya. Selanjutnya, beri warna pertama pada simpul-simpul yang bertetangga dengan simpul yang diberi warna kedua tadi. Lakukan proses ini sampai semua simpul diwarnai. Dengan demikian, dua warna sudah cukup untuk mewarnai simpul setiap pohon sehingga tidak ada dua simpul yang bertetangga mempunyai warna yang sama. Dengan kata lain, pohon mempunyai bilangan kromatik $2.$ $\blacksquare$
Sebagai contoh, berikut ini merupakan pohon dengan $7$ simpul dan pewarnaan simpulnya dengan hanya menggunakan dua warna, yaitu merah dan biru.
Berikutnya, kita definisikan terminologi baru yang berkaitan dengan pohon.
Definisi: Hutan
Secara sekilas, kita mungkin menganggap bahwa definisi pohon dan hutan mirip. Yang membedakannya adalah keterhubungan grafnya. Pohon harus berupa graf terhubung, tetapi hutan tidak mengharuskannya. Dari sini, kita tahu bahwa syarat graf untuk menjadi pohon lebih ketat dibandingkan menjadi hutan. Lebih lanjut, semua pohon merupakan hutan, tetapi tidak semua hutan merupakan pohon.
Sebagai contoh, perhatikan dua model graf berikut.
Graf $G$ dan $H$ keduanya merupakan hutan karena sama-sama tidak memuat siklus. Namun, $G$ merupakan pohon, sedangkan $H$ bukan pohon karena grafnya tidak terhubung. Dapat dilihat bahwa $H$ merupakan graf takterhubung dengan $2$ komponen.
Misalkan $G = (V, E)$ merupakan graf tak-berarah terhubung yang bukan pohon, artinya $G$ memuat siklus, setidaknya satu. $G$ dapat diubah menjadi pohon $T = (V_T, E_T)$ dengan cara memutuskan siklus-siklus yang ada. Secara teknis, tinjau suatu siklus di $T,$ kemudian hapus satu sisi dari siklus tersebut sehingga siklusnya sekarang berkurang satu. Lakukan proses serupa sampai tidak ditemukan siklus lagi di $G.$ Berdasarkan definisi pohon, sekarang $G = T$ merupakan pohon, atau lebih spesifik, pohon merentang.
Definisi: Pohon Merentang
Dengan kata lain, jika subgraf merentang (spanning subgraph) dari suatu graf terhubung merupakan pohon, maka subgraf merentang tersebut dinamai pohon merentang. Sebagai contoh, diberikan graf $G$ dan beberapa pohon merentangnya.
Beberapa teorema penting terkait pohon diberikan sebagai berikut.
Teorema: Banyak Simpul dan Sisi pada Pohon
Teorema tersebut akan dibuktikan dengan menggunakan induksi matematika.
Misalkan $n$ merupakan bilangan asli. Misalkan juga $P(n)$ menyatakan proposisi bahwa pohon dengan $n$ simpul memiliki $n-1$ sisi.
Langkah Basis:
Untuk $n = 1,$ $P(1)$ benar karena pohon dengan $1$ simpul membentuk graf trivial yang jelas tidak memiliki sisi $($sisinya sebanyak $0).$
Langkah Induktif:
Ambil sembarang bilangan asli $k.$ Asumsikan $P(k)$ benar, yaitu proposisi bahwa pohon dengan $k$ simpul memiliki $k-1$ sisi. Akan dibuktikan bahwa $P(k+1)$ benar, yaitu proposisi bahwa pohon dengan $k+1$ simpul memiliki $k$ sisi.
Misalkan pohon $T$ memiliki $k+1$ simpul. Karena pohon merupakan graf hingga, daun dari $T$ pasti ada, sebutlah $v.$ Misalkan $w$ merupakan induk dari $v.$ Dengan menghilangkan simpul $v$ dan sisi $\{w, v\}$ dari $T,$ diperoleh pohon baru $T’$ yang hanya karena graf yang dihasilkan masih terhubung dan tidak memuat siklus. Jelas bahwa $T’$ memiliki $k$ simpul . Menurut hipotesis induksi, $T’$ memiliki $k-1$ sisi. Akibatnya, $T$ memiliki $k$ sisi karena banyak sisi $T$ satu lebihnya dari $T’,$ yaitu ditambah dengan sisi yang menghubungkan $v$ dan $w$ tadi. Jadi, $P(k+1)$ benar.
Menurut prinsip induksi matematika, $P(n)$ benar untuk setiap bilangan asli $n.$ Dengan kata lain, pohon dengan $n$ simpul memiliki $n-1$ sisi. $\blacksquare$
Teorema: Ketaksamaan Kardinalitas Himpunan Simpul dan Sisi
Misalkan $G = (V, E)$ merupakan graf sederhana dan terhubung. Jika $G$ tidak memuat siklus, $G$ adalah pohon. Dengan menggunakan teorema terkait banyak simpul dan sisi pada pohon, diperoleh $|V(G)| = |E(G)|+1$ sehingga proposisi terbukti benar.
Sekarang misalkan $G$ memuat siklus, katakanlah $C.$ Pilih $e \in E(C)$ dan konstruksi graf $G_1 = G \setminus \{e\},$ yaitu graf $G$ yang tidak memuat sisi $e.$ Asumsikan $G_1$ tidak memuat siklus lagi, artinya $G_1$ merupakan pohon. Karena $e$ merupakan sisi pembentuk siklus, penghapusan sisi $e$ membuat $G_1$ masih tetap terhubung. Jelas bahwa $|E(G_1)| < |E(G)|.$ Akibatnya, diperoleh
$$|V(G)| = |V(G_1)| = |E(G_1)| + 1 < |E(G)| + 1.$$Jadi, $|V(G)| < |E(G)| + 1.$ Lebih lanjut, jika $G_1$ masih memuat siklus, lakukan proses yang serupa dengan menghilangkan sisi pembentuk siklusnya.
Dari sini, terbukti bahwa $|V(G)| \le |E(G)|+1.$ Kesamaan tercapai ketika $G$ merupakan pohon. $\blacksquare$
Teorema: Daun pada Pohon Taktrivial
Misalkan $T = (V, E)$ merupakan pohon taktrivial dengan $n \ge 2$ simpul. Dengan menggunakan metode kontradiksi, andaikan $T$ memiliki kurang dari dua daun. Jelas bahwa $T$ pasti memiliki satu daun karena jika tidak, siklus akan muncul sehingga bertentangan dengan definisi pohon. Misalkan daun tersebut dinamai $\ell.$
Tinjau lintasan terpanjang di $T$ dengan simpul awal $\ell$ dan simpul akhir $v_k \in V(T),$ yaitu $$(v_0 = \ell, v_1, \cdots, v_{k-1}, v_k).$$Karena $T$ hanya memiliki satu daun $\ell,$ simpul $v_k$ memiliki tetangga selain $v_{k-1},$ katakanlah $v_{k+1}.$ Akibatnya, lintasan dapat diperpanjang lagi menjadi $$(v_0 = \ell, v_1, \cdots, v_{k-1}, v_k, v_{k+1}).$$Hal ini kontradiktif dengan fakta bahwa kita sebelumnya sudah membuat lintasan terpanjang. Jadi, pengandaian salah. Disimpulkan bahwa pohon memiliki paling sedikit dua daun. $\blacksquare$
Di bawah ini telah disediakan sejumlah soal dan pembahasan tentang pohon. Sebagian soal dibuat oleh penulis sendiri dan sebagian lainnya diadaptasi dari literatur.
Baca: Istilah Lengkap dalam Teori Graf
Artikel ini ditulis berdasarkan beberapa sumber. Salah satu sumber berbahasa Indonesia yang digunakan adalah buku “Matematika Diskrit” karya Rinaldi Munir. Untuk sumber berbahasa Inggris, salah satu yang digunakan adalah buku “Discrete Mathematics and Its Applications” yang ditulis oleh Kenneth H. Rosen. Oleh karena itu, untuk meminimalisasi kesalahan penafsiran, padanan untuk beberapa kata/istilah diberikan dalam tabel berikut.
$$\begin{array}{ccc} \hline \text{No.} & \text{Bahasa Indonesia} & \text{Bahasa Inggris} \\ \hline 1. & \text{Graf Terhubung} & \text{Connected Graph} \\ 1. & \text{Pohon} & \text{Tree} \\ 2. & \text{Pohon Bebas} & \text{Free Tree} \\ 3. & \text{Pohon Berakar} & \text{Rooted Tree} \\ 2. & \text{Hutan} & \text{Forest} \\ 3. & \text{Daun} & \text{Leaf} \\ 4. & \text{Anak} & \text{Children} \\ 5. & \text{Induk} & \text{Parent} \\ 6. & \text{Saudara Kandung} & \text{Sibling} \\ 7. & \text{Leluhur} & \text{Ancestor} \\ 8. & \text{Keturunan} & \text{Descendant} \\ 8. & \text{Simpul Dalam} & \text{Internal Vertex} \\ 9. & \text{Subpohon} & \text{Subtree} \\ 10. & \text{Pohon m-er} & \text{m-ary Tree} \\ 11. & \text{Pohon Biner} & \text{Binary Tree} \\ 12. & \text{Pohon Berakar Terurut} & \text{Ordered Rooted Tree} \\ 13. & \text{Anak Kiri} & \text{Left Child} \\ 14. & \text{Anak Kanan} & \text{Right Child} \\ 15. & \text{Subpohon Kiri} & \text{Left Subtree} \\ 16. & \text{Subpohon Kanan} & \text{Right Subtree} \\ 17. & \text{Tingkat} & \text{Level} \\ 18. & \text{Ketinggian} & \text{Height} \\ 19. & \text{Seimbang} & \text{Balanced} \\ \hline \end{array}$$
Today Quote
Baca: Soal dan Pembahasan – Teori Dasar Graf
Baca: Istilah Lengkap dalam Teori Graf
Bagian Pilihan Ganda
Soal Nomor 1
Dari lima model graf berikut, manakah graf yang tergolong pohon?
Graf pada opsi A dan B merupakan graf sederhana, tetapi keduanya bukan pohon karena memuat siklus (salah satunya yang berupa bangun segitiga). Graf pada opsi C merupakan pohon karena tidak memuat siklus dan juga terhubung. Graf pada opsi D bukan graf sederhana karena memuat gelang sehingga bukan tergolong pohon. Graf pada opsi E juga bukan graf sederhana karena memuat sisi rangkap. Lebih lanjut, graf tersebut takterhubung sehingga jelas bukan tergolong pohon.
(Jawaban C)
Soal Nomor 2
Misalkan pohon $T$ dan $U$ masing-masing memiliki $5.000$ simpul dan $5.001$ simpul. Jika $T$ dan $U$ merupakan graf yang saling lepas, gabungan dari keduanya akan membentuk hutan yang memuat sisi sebanyak $\cdots \cdot$
A. $5.000$ D. $10.001$
B. $5.001$ E. $10.003$
C. $9.999$
Banyak sisi yang dimiliki suatu pohon sama dengan satu kurangnya dari banyak simpul. Karena $T$ memiliki $5.000$ simpul, sisinya ada sebanyak $4.999.$ Begitu juga dengan $U$ yang memiliki $5.001$ simpul sehingga sisinya ada sebanyak $5.000.$ Karena $T$ dan $U$ saling lepas (tidak ada simpul maupun sisi yang sama), banyak sisi semuanya ada $4.999 + 5.000 = 9.999.$ Jadi, ada $\boxed{9.999}$ sisi pada hutan yang terbentuk dari gabungan dua pohon tersebut.
(Jawaban C)
Soal Nomor 3
Suatu pohon mempunyai $2n$ simpul berderajat $1,$ $3n$ simpul berderajat $2,$ dan $n$ simpul berderajat $3.$ Banyak simpul dan sisi dari pohon tersebut berturut-turut adalah $\cdots \cdot$
A. $13$ dan $12$
B. $12$ dan $11$
C. $10$ dan $9$
D. $8$ dan $7$
E. $6$ dan $5$
Misalkan pohon tersebut dinotasikan $T = (V, E).$ Menurut lema jabat tangan, jumlah derajat semua simpul dari setiap graf adalah $2$ kali banyak sisi yang dimiliki graf tersebut. Dengan demikian,
$$\begin{aligned} 2|E| & = (2n \times 1) + (3n \times 2) + (n \times 3) \\ 2|E| & = 2n + 6n + 3n \\ 2|E| & = 11n. && (\cdots 1)\end{aligned}$$Karena banyak sisi yang dimiliki pohon sama dengan satu kurangnya dari banyak simpul, diperoleh
$$|E| = (2n + 3n + 1)-1 = 6n-1.~~~~~~~~~~~~(\cdots 2)$$Substitusikan persamaan $(2)$ pada $(1)$ menghasilkan
$$\begin{aligned} 2(6n-1) & = 11n \\ 12n-2 & = 11n \\ n & = 2. \end{aligned}$$Jadi, banyak simpulnya adalah $6n = 6(2) = 12,$ sedangkan banyak sisinya adalah $12-1=11.$
(Jawaban B)
Soal Nomor 4
Misalkan pohon $T$ memiliki $49$ sisi. Satu sisi dari $T$ dihilangkan sehingga terbentuk dua pohon yang saling lepas, katakanlah $T_1$ dan $T_2.$ Jika $T_1$ dan $T_2$ memuat banyak simpul yang sama, maka banyak sisi dari $T_1$ adalah $\cdots \cdot$
A. $24$ C. $26$ E. $49$
B. $25$ D. $48$
Misalkan pohon $T$ memiliki $49$ sisi. Ini berarti banyak simpul yang dimuat di $T$ adalah $49 + 1 = 50.$ Karena satu sisi dihilangkan, diperoleh pohon yang saling lepas, yaitu $T_1$ dan $T_2.$ Agar banyak simpulnya sama, $T_1$ dan $T_2$ masing-masing harus memuat $50 \div 2 = 25$ simpul. Akibatnya, $T_1$ memiliki $25-1=24$ sisi.
(Jawaban A)
Bagian Uraian
Soal Nomor 1
Misalkan $T$ merupakan pohon dengan $60$ sisi. Pembuangan suatu sisi tertentu dari $T$ menghasilkan dua pohon $T_1$ dan $T_2.$ Jika banyak simpul pada $T_1$ sama dengan banyak sisi pada $T_2,$ tentukan banyak simpul dan banyak sisi pada $T_1$ dan $T_2.$
Misalkan pohon $T$ memiliki $60$ sisi. Satu sisi dari $T$ dibuang sehingga diperoleh $T_1$ dan $T_2.$ Karena banyak sisi pada pohon sama dengan satu kurangnya dari banyak simpul, dapat kita misalkan $T_1$ memiliki $m$ simpul dan $m-1$ sisi, sedangkan $T_2$ memiliki $n$ simpul dan $n-1$ sisi. Banyak sisi secara keseluruhan adalah $60-1=59$ sehingga diperoleh persamaan $(m-1)+(n-1) = 59,$ atau $m+n=61.$
Karena diketahui banyak simpul pada $T_1$ sama dengan banyak sisi pada $T_2,$ didapat $m = n-1.$ Dari sini, diperoleh $(n-1)+n = 61$ sehingga haruslah $n = 31.$ Akibatnya, $m = 30.$
Jadi, $T_1$ memiliki $30$ simpul dan $29$ sisi, sedangkan $T_2$ memiliki $31$ simpul dan $30$ sisi.
Soal Nomor 2
Misalkan $m$ dan $n$ merupakan bilangan bulat positif. Graf bipartit lengkap $K_{m, n}$ manakah yang merupakan pohon?
Misalkan $m$ dan $n$ merupakan bilangan asli. Graf bipartit lengkap $K_{m, n}$ memiliki banyak simpul $m + n$ dan banyak sisi $mn.$ Agar graf tersebut dapat digolongkan sebagai pohon, banyak sisi harus satu kurangnya dari banyak simpul. Dari sini, diperoleh
$$\begin{aligned} mn & = (m+n)-1 \\ mn-m-n+1 &= 0 \\ (m-1)(n-1) & = 0 \end{aligned}$$Dari persamaan terakhir, diperoleh $m = 1$ atau $n = 1.$ Dengan kata lain, graf bipartit lengkap $K_{m, n}$ merupakan pohon jika $m$ atau $n$ salah satunya bernilai $1.$ Secara umum, $K_{m, 1}$ merupakan pohon untuk setiap bilangan bulat positif $m.$
Soal Nomor 3
Buktikan bahwa setiap sisi dari pohon merupakan jembatan.
Misalkan $T$ merupakan pohon. Dengan menggunakan metode kontradiksi, andaikan terdapat sisi $T$, katakanlah $\{v, w\},$ yang bukan jembatan. Akibatnya, penghapusan sisi tersebut membuat $T$ tetap terhubung. Dengan kata lain, jika $G’$ merupakan graf $G$ dengan sisi $\{v, w\}$ yang dihilangkan, maka $G’$ terhubung. Dengan demikian, terdapat suatu lintasan yang menghubungkan simpul $v$ dan $w$ di $G’.$ Lintasan tersebut bersama-sama dengan $\{v, w\}$ membentuk siklus di $G.$ Hal ini kontradiktif dengan definisi pohon sebagai graf yang tidak memiliki siklus. Jadi, pengandaian salah. Disimpulkan bahwa setiap sisi dari pohon merupakan jembatan. $\blacksquare$
Soal Nomor 4
Buktikan bahwa jika $P = \{v_0, v_1, v_2, \cdots, v_n\}$ merupakan lintasan terpanjang dari pohon $T,$ maka $\text{deg}(v_0) = \text{deg}(v_n) = 1.$
Misalkan $P = \{v_0, v_1, v_2, \cdots, v_n\}$ merupakan lintasan terpanjang dari pohon $T.$ Dengan menggunakan metode kontradiksi, andaikan $\text{deg}(v_0) \neq 1$ atau $\text{deg}(v_n) \neq 1.$ Jelas bahwa $v_0$ dan $v_n$ bukan simpul terpencil sehingga $\text{deg}(v_0) \neq 0$ atau $\text{deg}(v_n) \neq 0.$
Sekarang andaikan $\text{deg}(v_0) > 1.$ Akibatnya, terdapat simpul $v_{k}$ selain $v_1$ sehingga $v_0$ bertetangga dengan $v_k.$ Dengan kata lain, terdapat sisi $e = \{v_k, v_0\}$ yang bukan sisi pembentuk lintasan $P.$ Ini artinya ada lintasan lain di pohon $T$ yang lebih panjang dari $P,$ yaitu $\{v_k, v_0, v_1, v_2, \cdots, v_n\}.$ Namun, hal ini kontradiktif dengan fakta bahwa $P$ merupakan lintasan terpanjang. Jadi, pengandaian salah.
Dengan cara yang serupa, andaikan $\text{deg}(v_n) > 1.$ Akibatnya, terdapat simpul $v_{n+1}$ selain $v_{n-1}$ sehingga $v_n$ bertetangga dengan $v_{n+1}.$ Dengan kata lain, terdapat sisi $e = \{v_n, v_{n+1}\}$ yang bukan sisi pembentuk lintasan $P.$ Ini artinya ada lintasan lain di pohon $T$ yang lebih panjang dari $P,$ yaitu $\{v_0, v_1, v_2, \cdots, v_n, v_{n+1}\}.$ Namun, hal ini kontradiktif dengan fakta bahwa $P$ merupakan lintasan terpanjang. Jadi, pengandaian salah.
Dari sini, disimpulkan bahwa $\text{deg}(v_0) = \text{deg}(v_n) = 1.$ $\blacksquare$
Soal Nomor 5
Suatu graf merupakan pohon jika dan hanya jika setiap pasangan simpul berbeda di graf tersebut terhubung oleh tepat satu lintasan.
Kita akan membuktikan proposisi di atas dari dua arah karena proposisi tersebut berupa biimplikasi.
Arah kiri:
Misalkan $T$ merupakan pohon. Akan dibuktikan bahwa setiap pasangan simpul berbeda di $T$ terhubung oleh tepat satu lintasan.
Karena $T$ terhubung berdasarkan definisi pohon, setiap pasangan simpul berbeda di $T$ terhubung oleh setidaknya satu lintasan. Berikutnya, akan dibuktikan bahwa lintasan tersebut tunggal. Dengan menggunakan metode kontradiksi, andaikan terdapat pasangan simpul berbeda di $T$, katakanlah $u$ dan $v,$ yang terhubung oleh dua lintasan $P$ dan $Q.$ Misalkan $v_i \in T$ merupakan simpul pertama di $P$ yang tidak termuat di $Q$ dan $v_{i + k}$ dengan $k \ge 1$ merupakan simpul berikutnya yang termuat di $P$ dan $Q.$ Akibatnya, lintasan $$(v_{i-1}, v_i, v_{i + 1}, \cdots, v_{i + k}, \cdots, v_{i-1})$$merupakan siklus yang terbentuk karena eksistensi lintasan $P$ dan $Q.$ Hal ini kontradiktif dengan permisalan bahwa $T$ merupakan pohon karena pohon seharusnya tidak memuat siklus. Jadi, pengandaian salah. Terbukti bahwa setiap pasangan simpul berbeda di $T$ terhubung oleh tepat satu lintasan.
Arah kanan:
Misalkan $T$ merupakan graf yang setiap pasangan simpul berbedanya terhubung oleh tepat satu lintasan. Akan ditunjukkan bahwa $T$ merupakan pohon. Karena setiap pasangan simpul berbeda di $T$ terhubung oleh suatu lintasan, menurut definisi, $T$ terhubung. Berikutnya, perlu ditunjukkan bahwa $T$ asiklik (tidak memuat siklus).
Dengan menggunakan metode kontradiksi, andaikan $T$ memuat siklus $C.$ Pilih simpul $u, v \in C$ dengan $u \neq v$ sehingga $$C = (c_0 = u, c_1, \cdots, c_i = v, \cdots, c_0 = u).$$Akibatnya, $C$ memuat dua lintasan dari $u$ ke $v$, yaitu lintasan $(c_0 = u, c_1, \cdots, c_i = v)$ dan lintasan $(c_i = v, c_{i-1}, \cdots, c_1, c_0 = u).$ Hal ini kontradiktif dengan permisalan bahwa $G$ merupakan graf yang setiap pasangan simpul berbedanya terhubung oleh tepat satu lintasan. Jadi, pengandaian salah. Disimpulkan bahwa $T$ tidak memuat siklus. Karena $T$ terhubung dan tidak memuat siklus, berdasarkan definisi, $T$ merupakan pohon. $\blacksquare$