Olimpiade Sains Provinsi (OSP) 2019 - Komputer, Nomor 1

Diberikan graf seperti Gambar 1 di bawah ini. Graf ini terdiri dari 6 simpul dan 7 garis yang menghubungkan antar simpul.

Pak Dengklek dapat menghapus tepat 1 garis antar simpul pada graf tersebut. Sebagai contoh, apabila garis antar simpul 2 dan 6 dihapus, maka dihasilkan graf G seperti pada Gambar 2 di atas. Setelah itu, Pak Dengklek akan memilih himpunan simpul H dari graf G, sehingga simpul-simpul pada H sebanyak mungkin, dan tidak ada satu pun simpul yang terhubung langsung dengan simpul lain. Sebagai contoh, untuk Gambar 2 di atas, H yang terpilih memiliki 3 simpul (dapat memilih simpul bernomor 3, 4, dan 6).

Untuk setiap konfigurasi G yang dapat dibentuk dari Graf Awal (Gambar 1), berapakah maksimal banyaknya simpul pada H yang mungkin?