Latihan 12.

Perhatikan graf berikut.
Sebuah graf dengan 11 simpul. Delapan simpul tersusun melingkar dan dihubungkan oleh delapan sisi yang membentuk keliling segi delapan. Tiga simpul lainnya tersusun dalam baris mendatar di pusat segi delapan. Sisi-sisi menghubungkan simpul atas dan bawah segi delapan dengan simpul dalam di kiri dan kanan. Simpul luar di kiri bertetangga dengan simpul dalam di kiri, sedangkan simpul luar di kanan bertetangga dengan simpul dalam di kanan. Keempat simpul lain pada segi delapan bertetangga dengan simpul pusat.
  1. Temukan sebuah lintasan Hamilton. Dapatkah lintasan tersebut diperluas menjadi siklus Hamilton?
  2. Apakah graf tersebut bipartit? Jika ya, berapa banyak simpul yang terdapat dalam setiap “bagian”?
  3. Gunakan jawaban Anda pada butir (b) untuk membuktikan bahwa graf tersebut tidak memiliki siklus Hamilton.
  4. Misalkan Anda memiliki graf bipartit \(G\) dengan salah satu bagian memiliki sedikitnya dua simpul lebih banyak daripada bagian lainnya. Buktikan bahwa \(G\) tidak memiliki lintasan Hamilton.
dalam konteks