Pada Gambar 1.13, kami memperlihatkan sekumpulan \(4\) garis pada bidang. Setiap pasang garis saling berpotongan, dan tidak ada titik pada bidang yang terletak pada lebih dari dua garis. Garis-garis ini membentuk \(11\) daerah.
Dengan batasan yang sama, berapa banyak daerah yang dibentuk oleh sekumpulan \(8947\) garis? Dapatkah susunan garis yang berbeda membentuk jumlah daerah yang berbeda?
Mandy mengatakan bahwa ia telah menemukan himpunan \(882\) titik pada bidang yang menentukan tepat \(752\) garis. Tobias membantah klaimnya. Siapa yang benar?
Ada banyak cara berbeda untuk menggambar sebuah graf pada bidang. Sebagian penggambaran mungkin memiliki sisi-sisi yang berpotongan, sedangkan yang lain tidak. Namun, terkadang perpotongan sisi harus muncul dalam setiap penggambaran. Perhatikan graf \(G\) yang ditunjukkan pada Gambar 1.16.
Graf dengan sepuluh simpul bernomor 1 sampai 10 dan lima belas sisi. Beberapa sisi saling berpotongan dalam gambar; titik-titik perpotongan tersebut bukan simpul.
Misalkan Sam dan Deborah mendapat soal pekerjaan rumah yang menanyakan apakah suatu graf tertentu dengan \(2843952\) simpul dan \(9748032\) sisi dapat digambar tanpa perpotongan sisi. Deborah hanya melihat jumlah simpul dan jumlah sisi, lalu mengatakan bahwa jawabannya adalah “tidak.” Sam mempertanyakan bagaimana Deborah bisa begitu yakin—tanpa memeriksa struktur graf itu dengan lebih saksama. Adakah cara bagi Deborah untuk membenarkan kesimpulan tegasnya?
