Berapa jumlah maksimum dan jumlah minimum simpul pada graf sederhana yang mempunyai 12 buah sisi dan tiap simpul berderajat ≥ 3?

Penjelasan: Pertanyaan: Berapa jumlah maksimum dan jumlah minimum simpul pada graf sederhana yang mempunyai 12 buah sisi dan tiap simpul berbeda? Solusi: Jumlah maksimum simpul Pada graf sederhana, setiap simpul terhubung dengan simpul lain paling banyak sebanyak n-1 simpul, dengan n adalah jumlah simpul pada graf. Hal ini dapat dinyatakan dengan rumus: d_max ≤ n - 1 di mana d_max adalah derajat maksimum simpul pada graf. Pada soal, diketahui bahwa derajat minimum simpul adalah 3. Maka, d_max ≥ 3. Dengan demikian, n ≤ d_max + 1 ≤ 4. Jumlah minimum simpul Pada graf sederhana, jumlah sisi minimal sama dengan setengah dari jumlah derajat seluruh simpul. Hal ini dapat dinyatakan dengan rumus: e ≥ n(d_min)/2 di mana e adalah jumlah sisi pada graf. Pada soal, diketahui bahwa jumlah sisi adalah 12 dan derajat minimum simpul adalah 3. Maka, 12 ≥ n(3)/2. Dengan demikian, n ≥ 8. Kesimpulan Jumlah maksimum simpul pada graf sederhana yang mempunyai 12 buah sisi dan tiap simpul berbeda adalah 4. Jumlah minimum simpul pada graf sederhana yang mempunyai 12 buah sisi dan tiap simpul berbeda adalah 8. Penjelasan tambahan Pada graf sederhana, setiap simpul tidak boleh terhubung dengan dirinya sendiri. Hal ini berarti bahwa matriks ketetanggaan graf sederhana harus berupa matriks diagonal nol. Dengan menggunakan rumus-rumus yang telah disebutkan di atas, dapat disimpulkan bahwa graf sederhana yang mempunyai 12 buah sisi dan tiap simpul berbeda hanya mungkin memiliki 4 atau 8 simpul. Kesimpulan Jumlah maksimum dan minimum simpul pada graf sederhana yang mempunyai 12 buah sisi dan tiap simpul berbeda adalah 4 dan 8.