Teori graf merupakan salah satu cabang ilmu matematika yang banyak digunakan, karena teori-teorinya dapat diterapkan pada cabang-cabang ilmu matematika yang lain atau untuk memecahkan masalah dalam kehidupan seharihari seperti penjadwalan mata kuliah, perbaikan jaringan telekomunikasi, dan lainlain. Salah satu pembahasan dalam teori graf yang masih jarang dibahas adalah tentang keterhubungan. Dalam penelitian sebelumnya keterhubungan yang dibahas hanya pada pembuktian-pembuktian teorema yang terkait saja. Kemudian dalam skripsi ini penulis mengembangkannya dengan membahas keterhubungan pada graf beraturan. Dalam kajian ini, graf beraturan yang digunakan adalah graf beraturan dua dan graf beraturan tiga. Keterhubungan dalam graf ada dua macam, yaitu keterhubungan titik dan keterhubungan sisi. Keterhubungan titik pada graf G yang dinotasikan dengan Gdidefenisikan dengan minimum titik yang apabila dihapus dari graf G akan membuat graf tersebut tidak terhubung atau menjadi graf trivial. Keterhubungan sisi pada graf G yang dinotasikan dengan Gadalah minimum sisi yang apabila dihapus dari graf G akan membuat graf tersebut tidak terhubung atau menjadi graf trivial. Pada pembahasan diperoleh suatu teorema yaitu:
1. Suatu graf Cn dengan order n ( n 3 ) beraturan 2 maka 2 n C atau keterhubungan titiknya adalah 2.
2. Suatu graf Cn dengan order n ( n 3 ) beraturan 2 maka 2 n C atau keterhubungan sisinya adalah 2.
3. Suatu graf n L dengan order n ( n 4 ) beraturan 3 maka 3 n L atau keterhubungan titiknya adalah 3.
4. Suatu graf n L dengan order n ( n 4) beraturan 3 maka 3 n L atau keterhubungan sisinya adalah 3. Untuk penulisan skripsi selanjutnya, penulis menyarankan untuk mengkaji masalah pola keterhubungan titik dan keterhubungan sisi pada graf beraturan secara umum.
