Jawaban:

Kita dapat mengikuti Kriteria Kuratowski untuk membuktikan bahwa G tidak planar. Secara singkat, Kriteria Kuratowski adalah sebagai berikut:

Jika graf G mengandung subgraf homeomorfik K3,3 atau K5 (yg artinya graf ini memiliki 3 jalur atau lebih yang sempurna atau 5 jalur atau lebih yang sempurna masing-masing) maka G tidak planar.

Kita dapat mencari semua jalur-jalur sempurna pada graf G dan mengecek apakah ada 3 atau lebih yang berbeda. Jika ada 3 atau lebih jalur sempurna, maka G tidak planar dan kita telah berhasil membuktikannya!