Solusi T.20.1.

Pada \(S_1\text{,}\) beberapa sambungan wajib dilalui secara diagonal, sehingga graf tetangga-4 terputus tetapi graf tetangga-8 memiliki satu komponen. Pada \(S_2\text{,}\) jalur bertangga pada gambar dapat ditelusuri seluruhnya dengan langkah horizontal atau vertikal, sehingga graf tetangga-4 terhubung; penambahan sisi diagonal tidak dapat memutusnya. Rubrik: jawaban harus menyertakan jejak titik atau pohon rentang pada masing-masing graf, bukan hanya empat label benar-salah.
in-context