## Keterhubungan Pelangi Kuat (𝒔𝒓𝒄)
pada Graf (𝟏 𝑺𝒑𝒍 − (𝑪 𝒏 )) untuk 𝟑 ≤ 𝒏 ≤ 𝟏𝟎
Ermita Rizki Albirri 1 , Robiatul Adawiyah 2 , Lela Nur Safrida 3 , Reza Ambarwati 4
1 Universitas Jember, ermitara@unej.ac.id
2 Universitas Jember 2 , robiatul@unej.ac.id
3 Universitas Jember 3 , lelanurs@unej.ac.id
4 Universitas Jember, reza.ambarwati@unej.ac.id
Abstract. Let G be nontrivial and connected graph. A total-coloured path is called as total-rainbow if its edges and internal vertices have distinct colours. For any two vertices 𝑢 and 𝑣 of  G,  a  rainbow 𝑢 − 𝑣 geodesic  in 𝐺 is  a  rainbow 𝑢 − 𝑣 path  of length 𝑑(𝑢, 𝑣) ,  where 𝑑(𝑢, 𝑣) is  the  distance  between 𝑢 and 𝑣 .  The  graph 𝐺 is strongly  rainbow  connected  if  there  exists  a  rainbow 𝑢 − 𝑣 geodesic  for  any  two vertices 𝑢 and 𝑣 in G. The strong rainbow connection number of 𝐺 , denoted 𝑠𝑟𝑐(𝐺) , is the minimum number of colors that are needed  in order to make 𝐺 strong rainbow connected. The result shows for 1 𝑆𝑝𝑙 − (𝐶 𝑛 ) and 3 ≤ 𝑛 ≤ 10 there exist a coloring where 𝑑𝑖𝑎𝑚(𝐺) = 𝑟𝑐(𝐺) = 𝑠𝑟𝑐(𝐺) ≤ 𝑚 and 𝑑𝑖𝑎𝑚(𝐺) ≤ 𝑟𝑐(𝐺) ≤ 𝑠𝑟𝑐(𝐺) ≤ 𝑚 with 𝑚 is the number of path in 1 𝑆𝑝𝑙 − (𝐶 𝑛 ) .
Keywords:  strong  rainbow  connection  number , split  graph, 1 𝑆𝑝𝑙 − (𝐶 𝑛 ) graph for 3 ≤ 𝑛 ≤ 10
Abstrak. Misalkan 𝐺 suatu graf nontrivial dan terhubung.  Suatu pewarnaan busur pada graf 𝐺 disebut pelangi ( rainbow) jika terdapat lintasan pelangi ( rainbow) yaitu lintasan yang pewarnaannya pada setiap busur bertetangga berbeda.  Jika pewarnaan busur 𝑐: 𝐸(𝐺) → {1,2, … , 𝑘}, 𝑘 ∈ Ν , membuat  lintasan ( path ) yang menghubungkan dua simpul di graf 𝐺 adalah lintasan pelangi  ( lintasan pelangi) maka banyak warna minimal 𝑘 yang  digunakan  disebut  sebagai  bilangan  keterhubungan  pelangi ( rainbow  connection  number), ditulis  sebagai 𝑟𝑐(𝐺) .  Jika  pewarnaannya  adalah pewarnaan  geodesic  pelangi  ( rainbow  geodesic) ,  yaitu  setiap  simpul 𝑢 dan 𝑣 terhubung  dengan  lintasan  pelangi  dengan  panjang 𝑑(𝑢, 𝑣) ,  maka  banyak  warna minimal  yang  digunakan  disebut  sebagai  bilangan  keterhubungan  pelangi  ( strong rainbow  connection  number ),  dan  ditulis  sebagai 𝑠𝑟𝑐(𝐺) .  Penelitian  ini  membahas 𝑠𝑟𝑐(𝐺) pada  graf 1 𝑆𝑝𝑙 − (𝐶 𝑛 ) .  Hasil  dari  penelitian  ini  menunjukkan  bahwa  pada graf 1 𝑆𝑝𝑙 − (𝐶 𝑛 ) untuk 3 ≤ 𝑛 ≤ 10 terdapat  pewarnaan  dimana 𝑑𝑖𝑎𝑚(𝐺) = 𝑟𝑐(𝐺) = 𝑠𝑟𝑐(𝐺) ≤ 𝑚 dan 𝑑𝑖𝑎𝑚(𝐺) ≤ 𝑟𝑐(𝐺) ≤ 𝑠𝑟𝑐(𝐺) ≤ 𝑚 dengan 𝑚 adalah jumlah busur pada graf 1 𝑆𝑝𝑙 − (𝐶 𝑛 ) .
Kata kunci: strong rainbow connection number , graf split, graf 1 𝑆𝑝𝑙 − (𝐶 𝑛 ) untuk 3 ≤ 𝑛 ≤ 10

## 1 Pendahuluan
Misalkan 𝐺 suatu graf nontrivial dan terhubung yang didefinisikan memiliki pewarnaan  busur  sebagai  berikut 𝑐: 𝐸(𝐺) → {1,2, … , 𝑘}, 𝑘 ∈ Ν .  Jika 𝑐 membuat lintasan (path) yang menghubungkan dua simpul di Graf 𝐺 adalah lintasan pelangi ( lintasan pelangi). Chartrand dkk (2008) [1], mendefinisikan bahwa graf 𝐺 yang memiliki  lintasan  pelangi (lintasan  pelangi) yang  diwarnai  dengan  minimal 𝑘 warna  disebut  bilangan  keterhubungan  pelangi (rainbow  connection  number (𝑟𝑐) ) . Lintasan geodesic pelangi adalah lintasan terpendek pada suatu graf 𝐺 yang memiliki  pewarnaan  pelangi.  Apabila  graf 𝐺 memiliki  lintasan  geodesic  pelangi maka  disebut  bilangan  keterhubungan  pelangi  kuat (strong  rainbow  connection number (𝑠𝑟𝑐) ) karena  pewarnaan  ini  lebih  kuat  daripada  hanya  terdapat  lintasan pelangi saja dalam graf 𝐺 .
S.K. Vaidya dkk [3], mendefinisikan graf split secara umum adalah graf yang diperoleh  dengan  menambahkan  beberapa  simpul 𝑣 baru  yaitu 𝑣′ yang bertetangga  dengan  setiap  simpul 𝑣 di 𝐺 .  Graf split-cycle (1 𝑆𝑝𝑙 − (𝐶 𝑛 )) adalah graf  lengkap  berupa  graf  lingkaran  sekaligus  graf  split  dengan  graf  di  luarnya yang  memiliki  simpul-simpul  yang  sama  sejajar  dengan  graf  lingkaran  seperti pada Gambar 1. Graf split-cycle (1 𝑆𝑝𝑙 − (𝐶 𝑛 )) memiliki himpunan simpul dalam {𝑣 1 , 𝑣 2 , … , 𝑣 𝑛 } yang diperoleh dengan menambahkan sebanyak 1 simpul baru 𝑣 𝑖,1 dengan 𝑖 adalah  banyak  simpul  pada 𝐶 𝑛 ,  sedemikian  hingga  masing-masing simpul  pada 𝑣 𝑖,1 bertetangga  dengan  setiap  simpul  pada 𝑣 𝑖 di 𝐶 𝑛 atau  bisa dikatakan  bahwa  himpunan  simpul {𝑣 1,1 , 𝑣 1,2 , … , 𝑣 1,𝑛 } adalah  himpunan  simpul luar.  Sehingga  terdapat  3  jenis  busur  pada  graf  ini  yaitu  busur 𝑣 𝑖 𝑣 𝑖+1 ,  busur 𝑣 𝑖−1 𝑣 𝑖,1 ,  dan  busur 𝑣 𝑖+1 𝑣 𝑖,1 untuk 𝑖 = 1,2, … , 𝑛 .  Untuk  busur 𝑣 𝑖 𝑣 𝑖+1 adalah himpunan  busur {𝑣 1 𝑣 2 , 𝑣 2 𝑣 3 , … , 𝑣 𝑛 𝑣 1 = 𝑣 𝑖 𝑣 𝑖+1 } .  Kemudian  busur 𝑣 𝑖−1 𝑣 𝑖 adalah himpunan  busur  { 𝑣 1 𝑣 2,1 , 𝑣 2 𝑣 3,1 , … , 𝑣 𝑛−1 𝑣 𝑛,1 , 𝑣 𝑛 𝑣 1,1 = 𝑣 𝑖−1 𝑣 𝑖,1 },  dan  untuk  busur 𝑣 𝑖+1 𝑣 𝑖,1 adalah  himpunan  busur {𝑣 2 𝑣 1,1 , 𝑣 3 𝑣 2,1 , … , 𝑣 𝑛 𝑣 𝑛−1,1 , 𝑣 1 𝑣 𝑛,1 = 𝑣 𝑖+1 𝑣 𝑖,1 } [2].  Berdasarkan teori rainbow connection number diketahui bahwa 𝑑𝑖𝑎𝑚(𝐺) ≤ 𝑟𝑐(𝐺) ≤ 𝑠𝑟𝑐(𝐺) ≤ 𝑚 dengan 𝑑𝑖𝑎𝑚 adalah  diameter  pada  graf  atau  lintasan terpanjang yang bisa dibuat pada graf dan 𝑚 adalah jumlah semua busur pada graf 𝐺 .

## 2 Hasil Pewarnaan
Teorema 1. Untuk setiap bilangan bulat 3 ≤ 𝑛 ≤ 10 ,
𝑠𝑟𝑐(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) = { ⌊ 𝑛 + 3 2 ⌋ , 𝑛 = 0,3𝑚𝑜𝑑4; 3 ≤ 𝑛 ≤ 9 𝑛 + 1 2 , 𝑛 = 1𝑚𝑜𝑑4;  𝑛 = 5,9 𝑛 + 2 2 , 𝑛 = 2𝑚𝑜𝑑4; 𝑛 = 6,10
Bukti:
 Kasus 1: untuk 𝑛 ∈ {3,4,5}

## Unisda Journal of Mathematics and Computer Science
Pada  kasus  ini,  bisa  dikatakan  untuk 𝑛 ≠ 2𝑚𝑜𝑑4 memiliki  bilangan keterhubungan pelangi kuat (𝑠𝑟𝑐) yang sama yaitu 3 (walaupun rumus (𝑠𝑟𝑐) nya berbeda).  Pembuktian 𝑠𝑟𝑐(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) = 3, 𝑢𝑛𝑡𝑢𝑘 𝑛 ∈ {3,4,5} mengikuti pembuktian 𝑟𝑐(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) = 3, 𝑢𝑛𝑡𝑢𝑘 𝑛 ∈ {3,4,5} akibat hal-hal berikut:
a. 𝑠𝑟𝑐(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) ≥ 𝑟𝑐(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) ≥ 𝑑𝑖𝑎𝑚(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) = 3
b. Berdasarkan  konstruksinya,  ditemukan  lintasan  yang  merupakan  geodesic rainbow yaitu:
1. Apabila  simpul 𝑢 merupakan  simpul  dalam  dan  simpul 𝑡 merupakan  simpul luar Bukti:  misalkan 𝑢 = 𝑣 𝑖 dan 𝑡 = 𝑣 𝑗,1 .  Maka  lintasan  berikut  pasti  geodesic rainbow:
▪ 𝑢 − 𝑡: 𝑣 𝑖 − 𝑣 𝑖+1 − 𝑣 𝑗,1 untuk 𝑗 = 𝑖 + 2 dan 𝑗 = 𝑖 + 3
▪ 𝑢 − 𝑡: 𝑣 𝑖 − 𝑣 𝑖+1 − 𝑣 𝑗,1 untuk 𝑗 = 𝑖
2. Apabila simpul 𝑢, 𝑡 merupakan simpul luar
Bukti: misalkan 𝑢 = 𝑣 𝑗,1 dan 𝑡 = 𝑣 𝑘,1 . Maka lintasan berikut pasti rainbow: ▪ 𝑢 − 𝑡: 𝑣 𝑗,1 − 𝑣 𝑖+1 − 𝑣 𝑖 − 𝑣 𝑘,1 untuk 𝑗 = 𝑖 dan 𝑘 = 𝑖 + 1 ▪ 𝑢 − 𝑡: 𝑣 𝑗,1 − 𝑣 𝑘,1 untuk 𝑗 = 𝑖 dan 𝑘 = 𝑖 + 1
3. Apabila simpul 𝑢, 𝑡 merupakan simpul dalam
Bukti: misalkan 𝑢 = 𝑣 𝑖 dan 𝑡 = 𝑣 𝑙 . Maka lintasan berikut pasti rainbow: ▪ 𝑢 − 𝑡: 𝑣 𝑖 − 𝑣 𝑙 untuk 𝑙 = 𝑖 + 1
Jadi terbukti bahwa untuk 𝑠𝑟𝑐(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) = 𝑛+3 2 untuk 3 ≤ 𝑛 ≤ 5 .
 Kasus 2: 𝑢𝑛𝑡𝑢𝑘 𝑛 = 6
Misalkan  untuk 𝑛 = 6 maka 𝑠𝑟𝑐(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) = 4 . Didefinisikan 𝑐: 𝐸(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) → {1,2,3,4} dengan 𝑐(𝑒 𝑖 ) sebagai  berikut: 𝑐(𝑣 𝑖 𝑣 𝑖+1 ) = 1 untuk 𝑖 ganjil, 𝑐(𝑣 𝑖 𝑣 𝑖+1 ) = 2 untuk 𝑖 genap, 𝑐(𝑣 𝑖−1 𝑣 𝑖,1 ) = 3 dan 𝑐(𝑣 𝑖,1 𝑣 𝑖+1 ) = 4 .    Sehingga 𝑠𝑟𝑐(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) ≤ 4 .  Kemudian  akan  ditunjukkan 𝑠𝑟𝑐(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) ≥ 4 . Karena 𝑠𝑟𝑐(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) ≥ 𝑟𝑐(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) ≥ 𝑑𝑖𝑎𝑚(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) = 3 untuk 𝑛 = 6 ,  maka 𝑠𝑟𝑐(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) ≥ 3 .  Asumsikan 𝑠𝑟𝑐(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) = 3 . Misalkan 𝑐′ adalah pewarnaan 3-rainbow.
o Kasus  2.1.  Tanpa  mengurangi  keumuman,  misalkan 𝑐′(𝑣 𝑖−1 𝑣 𝑖,1 ) ≠ 𝑐′(𝑣 𝑖+1 𝑣 𝑖,1 ) , 𝑐′(𝑣 𝑖−1 𝑣 𝑖,1 ) = 1 dan 𝑐′(𝑣 𝑖+1 𝑣 𝑖,1 ) =  2 untuk 1 ≤ 𝑖 ≤ 𝑛 dengan 𝑛 = 6 . Selanjutnya akan dilihat lintasan-lintasan sebagai berikut:
• Apabila  simpul 𝑢 merupakan  simpul  dalam  dan  simpul 𝑡 merupakan  simpul luar. Misalkan 𝑢 = 𝑣 𝑖 dan 𝑡 = 𝑣 𝑗,1 .
▪ Kemudian akan dilihat lintasan 𝑢 − 𝑡: 𝑣 1 − 𝑣 3,1 . Karena 𝑐′(𝑣 𝑖−1 𝑣 𝑖,1 ) = 1 dan 𝑐′(𝑣 𝑖+1 𝑣 𝑖,1 ) =  2 ,  maka  hal  ini  memaksakan 𝑐 ′ ( 𝑣 1 𝑣 2 ) = 3 .  Hal  ini  juga berlaku untuk 𝑐 ′ ( 𝑣 𝑖 𝑣 𝑖+1 ) = 3 . Sehingga 𝑣 1 − 𝑣 3,1 menjadi geodesic rainbow. ▪ Selanjutnya  akan  dilihat  lintasan 𝑢 − 𝑡: 𝑣 1 − 𝑣 4,1 .  Karena 𝑐 ′ ( 𝑣 𝑖 𝑣 𝑖+1 ) = 3 , maka mengakibatkan 𝑣 1 − 𝑣 4,1 tidak menjadi geodesic rainbow. Maka hal ini kontradiksi dengan asumsi awal.
• Apabila  simpul 𝑢, 𝑡 merupakan  simpul  luar.  Misalkan 𝑢 = 𝑣 𝑗,1 dan 𝑡 = 𝑣 𝑘,1 . Maka karena 𝑐 ′ ( 𝑣 1 𝑣 2 ) = 3 lintasan-lintasan di bawah ini:

## Unisda Journal of Mathematics and Computer Science
▪ 𝑢 − 𝑡: 𝑣 1,1 − 𝑣 2 − 𝑣 1 − 𝑣 3,1 adalah geodesic rainbow.
▪ Selanjutnya  akan  dilihat  lintasan 𝑢 − 𝑡: 𝑣 1,1 − 𝑣 2 − 𝑣 3 − 𝑣 4,1 .  Sehingga, karena 𝑐 ′ ( 𝑣 1 𝑣 2 ) = 3 , maka lintasan tersebut geodesic rainbow. Terbukti.
• Apabila simpul 𝑢, 𝑡 merupakan simpul dalam.  Misalkan 𝑢 = 𝑣 𝑖 dan 𝑡 = 𝑣 𝑙 .
▪ Akan  dilihat  lintasan 𝑢 − 𝑡: 𝑣 1 − 𝑣 3 .  Maka  akan  menjadi  geodesic  rainbow jika 𝑢 − 𝑡: 𝑣 1 − 𝑣 2,1 − 𝑣 3 .
▪ Akan  dilihat  lintasan 𝑢 − 𝑡: 𝑣 1 − 𝑣 4 .  Maka  akan  menjadi  geodesic  rainbow jika 𝑢 − 𝑡: 𝑣 1 − 𝑣 2 − 𝑣 3,1 − 𝑣 4 . Terbukti.
Karena  tidak  semua  asumsi  awal  itu  terbukti  benar,  maka  hal  ini  dianggap kontradiksi dengan asumsi awal.
o Kasus  2.2.  Tanpa  mengurangi  keumuman,  misalkan 𝑐′(𝑣 𝑖−1 𝑣 𝑖,1 ) = 𝑐′(𝑣 𝑖+1 𝑣 𝑖,1 ) = 1 untuk ≤ 𝑖 ≤ 𝑛 dengan 𝑛 = 6 .  Oleh  karena  itu,  hal  ini memaksakan 𝑠 ′ ( 𝑣 𝑖 𝑣 𝑖+1 ) = 2 untuk 1 ≤ 𝑖 ≤ 6; 𝑖 𝑔𝑎𝑛𝑗𝑖𝑙 dan 𝑠 ′ ( 𝑣 𝑖 𝑣 𝑖+1 ) = 3 untuk 1 ≤ 𝑖 ≤ 6; 𝑖 𝑔𝑒𝑛𝑎𝑝 . Selanjutnya akan dilihat lintasan berikut:
• Apabila  simpul 𝑢 merupakan  simpul  dalam  dan  simpul 𝑡 merupakan  simpul luar. Misalkan 𝑢 = 𝑣 𝑖 dan 𝑡 = 𝑣 𝑗,1 . ▪ Kemudian akan dilihat lintasan 𝑢 − 𝑡: 𝑣 1 − 𝑣 3,1 . Berdasarkan asumsi di atas, lintasannya  menjadi 𝑣 1 − 𝑣 2 − 𝑣 3,1 .  Sehingga 𝑣 1 − 𝑣 3,1 menjadi  geodesic rainbow.
▪ Selanjutnya akan dilihat lintasan 𝑢 − 𝑡: 𝑣 1 − 𝑣 4,1 . Karena didapatkan lintasan 𝑣 1 − 𝑣 2 − 𝑣 3 − 𝑣 4,1 maka  mengakibatkan 𝑣 1 − 𝑣 4,1 menjadi  geodesic rainbow. Terbukti.
• Apabila simpul 𝑢, 𝑡 merupakan simpul luar. Misalkan 𝑢 = 𝑣 𝑗,1 dan 𝑡 = 𝑣 𝑘,1 . ▪ Akan  dilihat  lintasan 𝑢 − 𝑡: 𝑣 1,1 − 𝑣 2 − 𝑣 1 − 𝑣 3,1 .  Sehingga,  karena 𝑐′(𝑣 𝑖−1 𝑣 𝑖,1 ) = 𝑐′(𝑣 𝑖+1 𝑣 𝑖,1 ) = 1 , maka tidak ada geodesic rainbow.
▪ Akan  dilihat  lintasan 𝑢 − 𝑡: 𝑣 1,1 − 𝑣 2 − 𝑣 3 − 𝑣 4,1 .  Sehingga,  karena 𝑐′(𝑣 𝑖−1 𝑣 𝑖,1 ) = 𝑐′(𝑣 𝑖+1 𝑣 𝑖,1 ) = 1 ,  maka  lintasan  tersebut  bukan  geodesic rainbow.
Hal ini kontradiksi dengan asumsi awal.
• Apabila simpul 𝑢, 𝑡 merupakan simpul dalam.  Misalkan 𝑢 = 𝑣 𝑖 dan 𝑡 = 𝑣 𝑙 . ▪ Akan  dilihat  lintasan 𝑢 − 𝑡: 𝑣 1 − 𝑣 3 .  Maka  akan  menjadi  geodesic  rainbow jika 𝑢 − 𝑡: 𝑣 1 − 𝑣 2,1 − 𝑣 3 .
▪ Akan  dilihat  lintasan 𝑢 − 𝑡: 𝑣 1 − 𝑣 4 .  Maka  jika 𝑢 − 𝑡: 𝑣 1 − 𝑣 2 − 𝑣 3,1 − 𝑣 4 ataupun 𝑢 − 𝑡: 𝑣 1 − 𝑣 2 − 𝑣 3 − 𝑣 4 tidak  menjadi  geodesic  rainbow.  Hal  ini kontradiksi dengan asumsi awal.
Karena  tidak  semua  asumsi  awal  itu  terbukti  benar,  maka  hal  ini  dianggap kontradiksi  dengan  asumsi  awal.Dengan  demikian 𝑠𝑟𝑐(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) ≥ 4 . Karena  berdasarkan  konstruksi  pewarnaan  diperoleh 𝑠𝑟𝑐(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) ≤ 4, maka 𝑠𝑟𝑐(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) = 4 untuk 𝑛 = 6 .
 Kasus 3: 𝑢𝑛𝑡𝑢𝑘 𝑛 ∈ {7,8,9}

## Unisda Journal of Mathematics and Computer Science
Pada pembuktian ini, untuk 𝑛 ≠ 2𝑚𝑜𝑑4 memiliki bilangan keterhubungan pelangi  kuat (𝑠𝑟𝑐) yang  sama  yaitu  5  (walaupun  rumus (𝑠𝑟𝑐) nya berbeda).  Misalkan 𝑠𝑟𝑐(𝐺) = 5 untuk 𝑛 ∈ {7,8,9} .  Definisikan  sebagai 𝑐(𝑒 𝑖 ) suatu pewarnaan 𝑐: 𝐸(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) → {1,2,3,4,5} dengan
𝑠(𝑣 𝑖 𝑣 𝑖+1 ) = 𝑖(𝑚𝑜𝑑 3) . Selanjutnya untuk 𝑐(𝑣 𝑖−1 𝑣 𝑖,1 ) = 4 dan 𝑐(𝑣 𝑖+1 𝑣 𝑖,1 ) = 5 .
o Kasus  3.1.  Untuk 𝑛 = 7 .  Karena 𝑑𝑖𝑎𝑚(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) = 3 ,  maka 3 ≤ 𝑟𝑐(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) ≤ 𝑠𝑟𝑐(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) ≤ 5 .  Sehingga  untuk  menunjukkan 𝑠𝑟𝑐(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) ≥ 5 ,  cukup  dibuktikan 𝑠𝑟𝑐(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) ≠ 4 .  Maka diasumsikan 𝑠𝑟𝑐(𝐺) = 4 .  Misalkan 𝑐′ adalah pewarnaan 4-rainbow.
• Tanpa mengurangi keumuman, misalkan 𝑐′(𝑣 𝑖−1 𝑣 𝑖,1 ) ≠ 𝑐′(𝑣 𝑖+1 𝑣 𝑖,1 ) .
Misalkan 𝑐′(𝑣 𝑖−1 𝑣 𝑖,1 ) = 1 dan 𝑐′(𝑣 𝑖+1 𝑣 𝑖,1 ) =  2 untuk 1 ≤ 𝑖 ≤ 𝑛 dengan 𝑛 = 7 . Selanjutnya akan dilihat lintasan-lintasan sebagai berikut:
- Apabila  simpul 𝑢 merupakan  simpul  dalam  dan  simpul 𝑡 merupakan  simpul luar. Misalkan 𝑢 = 𝑣 𝑖 dan 𝑡 = 𝑣 𝑗,1 . ▪ Kemudian  akan  dilihat  lintasan 𝑢 − 𝑡: 𝑣 1 − 𝑣 5,1 .  Maka  hal  ini  memaksakan 𝑐 ′ ( 𝑣 1 𝑣 2 ) = 3; 𝑐 ′ ( 𝑣 2 𝑣 3 ) = 4 .  Begitu  pula  untuk  pewarnaan  busur-busur  pada subgraf 𝐶 7 selanjutnya melingkar searah jarum jam. Sehingga 𝑣 1 − 𝑣 2 − 𝑣 3 − 𝑣 4 − 𝑣 5,1 tidak menjadi geodesic rainbow.
▪ Selanjutnya  akan  dilihat  lintasan 𝑢 − 𝑡: 𝑣 1 − 𝑣 4,1 .  Berdasarkan  pewarnaan subgraf 𝐶 7 ,  maka  mengakibatkan 𝑣 1 − 𝑣 2 − 𝑣 3 − 𝑣 4,1 menjadi  geodesic rainbow.Maka hal ini kontradiksi dengan asumsi awal.
- Apabila  simpul 𝑢, 𝑡 merupakan  simpul  luar.  Misalkan 𝑢 = 𝑣 𝑗,1 dan 𝑡 = 𝑣 𝑘,1 . Maka lintasan-lintasan di bawah ini:
▪ 𝑢 − 𝑡: 𝑣 1,1 − 𝑣 2 − 𝑣 3 − 𝑣 4,1 adalah geodesic rainbow.
▪ 𝑢 − 𝑡: 𝑣 1,1 − 𝑣 7 − 𝑣 6 − 𝑣 5,1 adalah geodesic rainbow. Terbukti.
- Apabila  simpul 𝑢, 𝑡 merupakan  simpul  dalam.  Misalkan 𝑢 = 𝑣 𝑖 dan 𝑡 = 𝑣 𝑙 . Berdasarkan pewarnaan 𝑐′ ,
▪ Akan dilihat lintasan 𝑢 − 𝑡: 𝑣 1 − 𝑣 7 − 𝑣 6,1 − 𝑣 5 menjadi geodesic rainbow. ▪ Akan  dilihat  lintasan 𝑢 − 𝑡: 𝑣 7 − 𝑣 3 .  Maka  akan  menjadi  geodesic  rainbow jika 𝑢 − 𝑡: 𝑣 7 − 𝑣 1,1 − 𝑣 2 − 𝑣 3 . Terbukti.
Karena  tidak  semua  asumsi  awal  itu  terbukti  benar,  maka  hal  ini  dianggap kontradiksi dengan asumsi awal.
• Tanpa mengurangi keumuman, misalkan 𝑐′(𝑣 𝑖−1 𝑣 𝑖,1 ) = 𝑐′(𝑣 𝑖+1 𝑣 𝑖,1 ) = 1 . Selanjutnya akan dilihat lintasan-lintasan sebagai berikut:
- Apabila  simpul 𝑢 merupakan  simpul  dalam  dan  simpul 𝑡 merupakan  simpul luar. Misalkan 𝑢 = 𝑣 𝑖 dan 𝑡 = 𝑣 𝑗,1 .
▪ Kemudian  akan  dilihat  lintasan u − t: v 1 − v 4,1 .  Maka  hal  ini  memaksakan c ′ ( v 1 v 2 ) = 2; c ′ ( v 2 v 3 ) = 3; c ′ ( v 3 v 4 ) = 4 . Begitu pula untuk pewarnaan busur- busur  pada  subgraf C 7 selanjutnya  melingkar  searah  jarum  jam.  Sehingga v 1 − v 2 − v 3 − v 4,1 menjadi geodesic rainbow.

## Unisda Journal of Mathematics and Computer Science
▪ Selanjutnya  akan  dilihat  lintasan u − t: v 1 − v 5,1 .  Berdasarkan  pewarnaan subgraf C 7 ,  maka  mengakibatkan v 1 − v 7 − v 6 − v 5,1 menjadi  geodesic rainbow.Terbukti.
- Apabila  simpul 𝑢, 𝑡 merupakan  simpul  luar.    Misalkan 𝑢 = 𝑣 𝑗,1 dan 𝑡 = 𝑣 𝑘,1 . Maka lintasan-lintasan di bawah ini:
▪ 𝑢 − t: v 1,1 − v 2 − v 1 − v 2,1 bukan geodesic rainbow.
▪ u − t: v 1,1 − v 7 − v 6 − v 5,1 bukan  geodesic  rainbow.  Maka  kontradiksi dengan asumsi awal.
- Apabila  simpul 𝑢, 𝑡 merupakan  simpul  dalam.  Misalkan 𝑢 = 𝑣 𝑖 dan 𝑡 = 𝑣 𝑙 . Berdasarkan pewarnaan 𝑐′ ,
▪ Akan  dilihat  lintasan u − t: v 7 − v 1 − v 2 ataupun u − t: v 7 − v 1,1 − v 2 bukan geodesic rainbow.
▪ Akan dilihat lintasan u − t: v 1 − v 5 . Maka akan menjadi geodesic rainbow jika u − t: v 1 − v 7 − v 6 − v 5 . Maka kontradiksi dengan asumsi awal. Karena  tidak  semua  asumsi  awal  itu  terbukti  benar,  maka  hal  ini  dianggap kontradiksi dengan asumsi awal. Sehingga terbukti bahwa 𝑠𝑟𝑐(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) ≥ 5 untuk 𝑛 = 7 .
o Kasus  3.2 . Untuk 𝑛 = 8 .  Karena 𝑑𝑖𝑎𝑚(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) = 4 ,  maka 4 ≤ 𝑟𝑐(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) ≤ 𝑠𝑟𝑐(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) ≤ 5 .  Akan  ditunjukkan 𝑠𝑟𝑐(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) ≥ 5 . Maka diasumsikan 𝑠𝑟𝑐(𝐺) = 4 .  Misalkan 𝑐′ adalah pewarnaan 4- rainbow.
• Tanpa mengurangi keumuman, misalkan c ′(𝑣 𝑖−1 𝑣 𝑖,1 ) ≠ 𝑐′(𝑣 𝑖+1 𝑣 𝑖,1 ) . Misalkan 𝑐′(𝑣 𝑖−1 𝑣 𝑖,1 ) = 1 dan 𝑐′(𝑣 𝑖+1 𝑣 𝑖,1 ) =  2 untuk 1 ≤ 𝑖 ≤ 𝑛 dengan 𝑛 = 8 . Selanjutnya akan dilihat lintasan-lintasan sebagai berikut:
- Apabila  simpul 𝑢 merupakan  simpul  dalam  dan  simpul 𝑡 merupakan  simpul luar. Misalkan 𝑢 = 𝑣 𝑖 dan 𝑡 = 𝑣 𝑗,1 .
▪ Kemudian akan dilihat lintasan u − t: v 1 − v 5,1 . Maka hal ini memaksakan c ′ ( v 1 v 2 ) = 3; c ′ ( v 2 v 3 ) = 4 .  Begitu  pula  untuk  pewarnaan  busur-busur pada subgraf C 8 selanjutnya melingkar searah jarum jam. Sehingga v 1 − v 2 − v 3 − v 4,1 − v 5 − v 4 − v 5,1 tidak menjadi geodesic rainbow.
▪ Selanjutnya akan dilihat lintasan u − t: v 1 − v 4,1 . Berdasarkan pewarnaan subgraf C 7 ,  maka  mengakibatkan v 1 − v 2 − v 3 − v 4,1 menjadi  geodesic rainbow. Maka hal ini kontradiksi dengan asumsi awal.
- Apabila  simpul 𝑢, 𝑡 merupakan  simpul  luar.    Misalkan 𝑢 = 𝑣 𝑗,1 dan 𝑡 = 𝑣 𝑘,1 . Maka lintasan-lintasan di bawah ini:
▪ u − t: v 1,1 − v 2 − v 3 − v 4,1 adalah geodesic rainbow.
▪ u − t: v 1,1 − v 7 − v 6 − v 5,1 adalah geodesic rainbow . Terbukti.
- Apabila  simpul 𝑢, 𝑡 merupakan  simpul  dalam.  Misalkan 𝑢 = 𝑣 𝑖 dan 𝑡 = 𝑣 𝑙 . Berdasarkan pewarnaan 𝑠′ ,
▪ Akan  dilihat  lintasan u − t: v 1 − v 8 − v 7 − v 6,1 − v 5 menjadi  geodesic rainbow.
▪ Akan dilihat lintasan u − t: v 1 − v 4 . Maka akan menjadi geodesic rainbow jika u − t: v 1 − v 2 − v 3,1 − v 4 . Terbukti.
Karena  tidak  semua  asumsi  awal  itu  terbukti  benar,  maka  hal  ini  dianggap kontradiksi dengan asumsi awal.
• Tanpa mengurangi keumuman, misalkan 𝑐′(𝑣 𝑖−1 𝑣 𝑖,1 ) = 𝑐′(𝑣 𝑖+1 𝑣 𝑖,1 ) = 1 .
Selanjutnya akan dilihat lintasan-lintasan sebagai berikut:
- Apabila  simpul 𝑢 merupakan  simpul  dalam  dan  simpul 𝑡 merupakan  simpul luar. Misalkan 𝑢 = 𝑣 𝑖 dan 𝑡 = 𝑣 𝑗,1 . ▪ Kemudian akan dilihat lintasan u − t: v 1 − v 4,1 . Maka hal ini memaksakan c ′ ( v 1 v 2 ) = 2; c ′ ( v 2 v 3 ) = 3; c ′ ( v 3 v 4 ) = 4 .  Begitu  pula  untuk  pewarnaan busur-busur  pada  subgraf C 8 selanjutnya  melingkar  searah  jarum  jam.
Sehingga v 1 − v 2 − v 3 − v 4,1 menjadi geodesic rainbow.
▪ Selanjutnya akan dilihat lintasan u − t: v 1 − v 5,1 . Berdasarkan pewarnaan subgraf C 8 ,  maka  mengakibatkan v 1 − v 2 − v 3 − v 4 − v 5,1 tidak  menjadi geodesic rainbow . Maka kontradiksi.
- Apabila  simpul 𝑢, 𝑡 merupakan  simpul  luar.    Misalkan 𝑢 = 𝑣 𝑗,1 dan 𝑡 = 𝑣 𝑘,1 . Maka lintasan-lintasan di bawah ini:
▪ u − t: v 1,1 − v 2 − v 1 − v 2,1 bukan geodesic rainbow.
▪ u − t: v 1,1 − v 8 − v 7 − v 6,1 bukan geodesic rainbow .
Maka kontradiksi dengan asumsi awal.
- Apabila  simpul 𝑢, 𝑡 merupakan  simpul  dalam.  Misalkan 𝑢 = 𝑣 𝑖 dan 𝑡 = 𝑣 𝑙 . Berdasarkan pewarnaan c ′ ,
▪ Akan  dilihat  lintasan u − t: v 1 − v 2 − v 3 − v 4 − v 5 ataupun u − t: v 1 − v 8 − v 7 − v 6 − v 5 bukan geodesic rainbow.
▪ Akan  dilihat  lintasan u − t: v 7 − v 3 .  Maka  bukan  geodesic  rainbow  pada u − t: v 7 − v 8 − v 1 − v 2 − v 3 . Maka kontradiksi dengan asumsi awal.
Karena  tidak  semua  asumsi  awal  itu  terbukti  benar,  maka  hal  ini  dianggap kontradiksi dengan asumsi awal. Sehingga terbukti bahwa 𝑠𝑟𝑐(1𝑆𝑝𝑙 − (𝐶 𝑛 )) ≥ 5 untuk 𝑛 = 8 .
o Kasus  3.3.  Untuk 𝑛 = 9 .  Karena 𝑑𝑖𝑎𝑚(1𝑆𝑝𝑙 − (𝐶 𝑛 )) = 4 ,  maka 4 ≤ 𝑟𝑐(1𝑆𝑝𝑙 − (𝐶 𝑛 )) ≤ 𝑠𝑟𝑐(1𝑆𝑝𝑙 − (𝐶 𝑛 )) ≤ 5 .  Akan  ditunjukkan 𝑠𝑟𝑐(1𝑆𝑝𝑙 − (𝐶 𝑛 )) ≥ 5 .  Maka  diasumsikan 𝑠𝑟𝑐(1𝑆𝑝𝑙 − (𝐶 𝑛 )) = 4 .    Misalkan 𝑐′ adalah pewarnaan 4-rainbow.
• Tanpa  mengurangi  keumuman,  misalkan 𝑐′(𝑣 𝑖−1 𝑣 𝑖,1 ) ≠ 𝑐′(𝑣 𝑖+1 𝑣 𝑖,1 ) .Misalkan 𝑐′(𝑣 𝑖−1 𝑣 𝑖,1 ) = 1 dan 𝑐′(𝑣 𝑖+1 𝑣 𝑖,1 ) =  2 untuk 1 ≤ 𝑖 ≤ 𝑛 dengan 𝑛 = 9 . Selanjutnya akan dilihat lintasan-lintasan sebagai berikut:
- Apabila  simpul 𝑢 merupakan  simpul  dalam  dan  simpul 𝑡 merupakan  simpul luar. Misalkan 𝑢 = 𝑣 𝑖 dan 𝑡 = 𝑣 𝑗,1 . ▪ Kemudian akan dilihat lintasan u − t: v 1 − v 5,1 . Maka hal ini memaksakan c ′ ( v 1 v 2 ) = 3; c ′ ( v 2 v 3 ) = 4 .  Begitu  pula  untuk  pewarnaan  busur-busur pada subgraf C 9 selanjutnya melingkar searah jarum jam. Sehingga v 1 − v 2 − v 3 − v 4,1 − v 5 − v 4 − v 5,1 tidak menjadi geodesic rainbow.
▪ Selanjutnya akan dilihat lintasan u − t: v 9 − v 3,1 . Berdasarkan pewarnaan subgraf C 9 , maka mengakibatkan v 8 − v 9 − v 1 − v 2 − v 3,1 bukan geodesic rainbow.

## Unisda Journal of Mathematics and Computer Science
Maka hal ini kontradiksi dengan asumsi awal.
- Apabila  simpul 𝑢, 𝑡 merupakan  simpul  luar.    Misalkan 𝑢 = 𝑣 𝑗,1 dan 𝑡 = 𝑣 𝑘,1 . Maka lintasan-lintasan di bawah ini:
▪ u − t: v 8,1 − v 9 − v 1 − v 2 − v 3,1 bukan geodesic rainbow.
▪ u − t: v 1,1 − v 9 − v 8 − v 7 − v 6,1 adalah geodesic rainbow. Kontradiksi.
- Apabila  simpul 𝑢, 𝑡 merupakan  simpul  dalam.  Misalkan 𝑢 = 𝑣 𝑖 dan 𝑡 = 𝑣 𝑙 . Berdasarkan pewarnaan 𝑐′ ,
▪ Akan  dilihat  lintasan u − t: v 1 − v 2 − v 3 − v 4,1 − v 5 menjadi  geodesic rainbow.
▪ Akan dilihat lintasan u − t: v 1 − v 6 . Maka akan menjadi geodesic rainbow jika u − t: v 1 − v 9 − v 8 − v 7,1 − v 6 . Terbukti.
Karena  tidak  semua  asumsi  awal  itu  terbukti  benar,  maka  hal  ini  dianggap kontradiksi dengan asumsi awal.
• Tanpa mengurangi keumuman, misalkan 𝑐′(𝑣 𝑖−1 𝑣 𝑖,1 ) = 𝑐′(𝑣 𝑖+1 𝑣 𝑖,1 ) = 1 .
Selanjutnya akan dilihat lintasan-lintasan sebagai berikut:
- Apabila  simpul 𝑢 merupakan  simpul  dalam  dan  simpul 𝑡 merupakan  simpul luar. Misalkan 𝑢 = 𝑣 𝑖 dan 𝑡 = 𝑣 𝑗,1 .
▪ Kemudian  akan  dilihat  lintasan u − t: v 1 − v 4,1 .  Maka  hal  ini  memaksakan c ′ ( v 1 v 2 ) = 2; c ′ ( v 2 v 3 ) = 3; c ′ ( v 3 v 4 ) = 4 . Begitu pula untuk pewarnaan busur- busur  pada  subgraf C 9 selanjutnya  melingkar  searah  jarum  jam.  Sehingga v 1 − v 2 − v 3 − v 4,1 menjadi geodesic rainbow.
▪ Selanjutnya  akan  dilihat  lintasan u − t: v 1 − v 5,1 .  Berdasarkan  pewarnaan subgraf C 9 ,  maka  mengakibatkan v 1 − v 2 − v 3 − v 4 − v 5,1 adalah  geodesic rainbow.Terbukti.
- Apabila  simpul 𝑢, 𝑡 merupakan  simpul  luar.    Misalkan 𝑢 = 𝑣 𝑗,1 dan 𝑡 = 𝑣 𝑘,1 . Maka lintasan-lintasan di bawah ini:
▪ u − t: v 1,1 − v 2 − v 1 − v 2,1 bukan geodesic rainbow.
▪ u − t: v 1,1 − v 9 − v 8 − v 7 − v 6,1 bukan geodesic rainbow.
Maka kontradiksi dengan asumsi awal.
- Apabila  simpul 𝑢, 𝑡 merupakan  simpul  dalam.  Misalkan 𝑢 = 𝑣 𝑖 dan 𝑡 = 𝑣 𝑙 . Berdasarkan pewarnaan 𝑐′ ,
▪ Akan  dilihat  lintasan u − t: v 1 − v 2 − v 3 − v 4 − v 5 bukan  geodesic rainbow.
▪ Akan  dilihat  lintasan u − t: v 9 − v 2 .  Maka  bukan  geodesic  rainbow  pada u − t: v 9 − v 1 − v 2 . Maka kontradiksi dengan asumsi awal.
Karena  tidak  semua  asumsi  awal  itu  terbukti  benar,  maka  hal  ini  dianggap kontradiksi dengan asumsi awal. Sehingga terbukti bahwa 𝑠𝑟𝑐(1𝑆𝑝𝑙 − (𝐶 𝑛 )) ≥ 5 untuk 𝑛 = 9 .  Dengan  demikian  terbukti  bahwa 𝑠𝑟𝑐(1𝑆𝑝𝑙 − (𝐶 𝑛 )) ≥ 5 . Berdasarkan  konstruksi  pewarnaan 𝑠 maka  diperoleh 𝑠𝑟𝑐(1𝑆𝑝𝑙 − (𝐶 𝑛 )) ≤ 5 . Sehingga terbukti bahwa 𝑠𝑟𝑐(1𝑆𝑝𝑙 − (𝐶 𝑛 )) = 5 untuk 𝑛 = {7,8,9} .
 Kasus 4: 𝑢𝑛𝑡𝑢𝑘 𝑛 = 10

## Unisda Journal of Mathematics and Computer Science
Misalkan untuk 𝑛 = 10 maka 𝑠𝑟𝑐(1𝑆𝑝𝑙 − (𝐶 𝑛 )) = 6 . Didefinisikan 𝑐: 𝐸(1 𝑆𝑝𝑙 − (𝐶 𝑛 )) → {1,2, … ,6} dengan 𝑐(𝑒 𝑖 ) sebagai  berikut: 𝑐(𝑣 𝑖 𝑣 𝑖+1 ) = 𝑖(𝑚𝑜𝑑4) , 𝑐(𝑣 𝑖−1 𝑣 𝑖,1 ) = 5 dan 𝑐(𝑣 𝑖,1 𝑣 𝑖+1 ) = 6 .    Kemudian  akan  ditunjukkan 𝑠𝑟𝑐(𝐺) ≥ 6 . Karena 𝑠𝑟𝑐(1𝑆𝑝𝑙 − (𝐶 𝑛 )) ≥ 𝑟𝑐(1𝑆𝑝𝑙 − (𝐶 𝑛 )) ≥ 𝑑𝑖𝑎𝑚(1𝑆𝑝𝑙 − (𝐶 𝑛 )) = 5 ,  maka 𝑠𝑟𝑐(1𝑆𝑝𝑙 − (𝐶 𝑛 )) ≥ 5 .  Asumsikan 𝑠𝑟𝑐(1𝑆𝑝𝑙 − (𝐶 𝑛 )) = 5 .  Misalkan 𝑐′ adalah pewarnaan 5-rainbow.
o Kasus  4.1.  Tanpa  mengurangi  keumuman,  misalkan 𝑐′(𝑣 𝑖−1 𝑣 𝑖,1 ) ≠ 𝑐′(𝑣 𝑖+1 𝑣 𝑖,1 ) . Misalkan 𝑐′(𝑣 𝑖−1 𝑣 𝑖,1 ) = 1 dan 𝑐′(𝑣 𝑖+1 𝑣 𝑖,1 ) =  2 untuk 1 ≤ 𝑖 ≤ 𝑛 dengan 𝑛 = 10 . Selanjutnya akan dilihat lintasan-lintasan sebagai berikut:
• Apabila  simpul 𝑢 merupakan  simpul  dalam  dan  simpul 𝑡 merupakan  simpul luar. Misalkan 𝑢 = 𝑣 𝑖 dan 𝑡 = 𝑣 𝑗,1 .
▪ Kemudian akan dilihat lintasan u − t: v 1 − v 5,1 . Maka hal ini memaksakan c ′ ( v 1 v 2 ) = 3; c ′ ( v 2 v 3 ) = 4; c ′ ( v 3 v 4 ) = 5 .  Begitu  pula  untuk  pewarnaan busur-busur  pada  subgraf C 10 selanjutnya  melingkar  searah  jarum  jam. Sehingga v 1 − v 2 − v 3 − v 4 − v 5,1 menjadi geodesic rainbow.
▪ Selanjutnya akan dilihat lintasan u − t: v 1 − v 6,1 . Berdasarkan pewarnaan subgraf C 10 ,  maka  mengakibatkan v 1 − v 2 − v 3 − v 4 − v 5 − v 6,1 ataupun v 1 − v 10 − v 9 − v 8 − v 7 − v 6,1 tidak menjadi geodesic rainbow.
▪ Maka hal ini kontradiksi dengan asumsi awal.
• Apabila  simpul 𝑢, 𝑡 merupakan  simpul  luar.  Misalkan 𝑢 = 𝑣 𝑗,1 dan 𝑡 = 𝑣 𝑘,1 . Maka lintasan-lintasan di bawah ini:
▪ u − t: v 9,1 − v 8 − v 7 − v 6 − v 5 − v 4,1 adalah geodesic rainbow.
▪ Selanjutnya  akan  dilihat  lintasan u − t: v 9,1 − v 3,1 .  Sehingga,  pewarnaan c′ ,  maka  lintasan v 9,1 − v 10 − v 1 − v 2 − v 3,1 tersebut  tidak  geodesic rainbow.
▪ Maka hal ini kontradiksi dengan asumsi awal.
• Apabila  simpul 𝑢, 𝑡 merupakan  simpul  dalam.    Misalkan 𝑢 = 𝑣 𝑖 dan 𝑡 = 𝑣 𝑙 . Berdasarkan pewarnaan 𝑐′ , ▪ Akan  dilihat  lintasan u − t: v 10 − v 1 − v 2,1 − v 3 − v 4 menjadi  geodesic rainbow.
▪ Akan  dilihat  lintasan u − t: v 10 − v 5 .  Maka  akan  menjadi  geodesic rainbow jika u − t: v 10 − v 9 − v 8 − v 7 − v 6,1 − v 5 . Terbukti.
Karena  tidak  semua  asumsi  awal  itu  terbukti  benar,  maka  hal  ini  dianggap kontradiksi dengan asumsi awal.
o Kasus  4.2.  Tanpa  mengurangi  keumuman,  misalkan 𝑐′(𝑣 𝑖−1 𝑣 𝑖,1 ) = 𝑐′(𝑣 𝑖+1 𝑣 𝑖,1 ) = 1 untuk ≤ 𝑖 ≤ 𝑛 dengan 𝑛 = 10 .  Oleh  karena  itu,  hal  ini memaksakan  pewarnaan 𝑣 𝑖 𝑣 𝑖+1 menjadi  pewarnaan  dengan  4  warna  yaitu {2,3,4,5} . Anggap pewarnaanya memutar searah jarum jam yang dimulai dari busur 𝑣 1 𝑣 2 . Selanjutnya akan dilihat lintasan berikut:
• Apabila  simpul 𝑢 merupakan  simpul  dalam  dan  simpul 𝑡 merupakan  simpul luar. Misalkan 𝑢 = 𝑣 𝑖 dan 𝑡 = 𝑣 𝑗,1 .

## Unisda Journal of Mathematics and Computer Science
▪ Kemudian  akan  dilihat  lintasan u − t: v 9 − v 4,1 .  Berdasarkan  asumsi  di atas, lintasannya menjadi v 9 − v 8 − v 7 − v 6 − v 5 − v 4,1 . Sehingga v 9 − v 4,1 menjadi geodesic rainbow.
▪ Selanjutnya  akan  dilihat  lintasan u − t: v 9 − v 3,1 .  Karena  didapatkan lintasan v 9 − v 1 − v 2 − v 3,1 maka  tidak  mengakibatkan v 9 − v 3,1 menjadi geodesic rainbow.
▪ Maka hal ini kontradiksi dengan asumsi awal.
• Apabila simpul 𝑢, 𝑡 merupakan simpul luar. Misalkan 𝑢 = 𝑣 𝑗,1 dan 𝑡 = 𝑣 𝑘,1 .
▪ Akan  dilihat  lintasan u − t: v 1,1 − v 2 − v 1 − v 3,1 .  Sehingga,  karena c′(v i−1 v i,1 ) = c′(v i+1 v i,1 ) = 1 , maka tidak ada geodesic rainbow.
▪ Akan  dilihat  lintasan u − t: v 1,1 − v 2 − v 3 − v 4,1 .  Sehingga,  karena c′(v i−1 v i,1 ) = c′(v i+1 v i,1 ) = 1 ,  maka  lintasan  tersebut  bukan  geodesic rainbow. Hal ini kontradiksi dengan asumsi awal.
• Apabila simpul 𝑢, 𝑡 merupakan simpul dalam.  Misalkan 𝑢 = 𝑣 𝑖 dan 𝑡 = 𝑣 𝑙 .
▪ Akan  dilihat  lintasan u − t: v 9 − v 3 .  Maka  jika u − t: v 9 − v 1 − v 2 − v 3 tidak  menjadi geodesic rainbow.
▪ Akan  dilihat  lintasan u − t: v 9 − v 4 .  Maka  jika u − t: v 9 − v 1 − v 2 − v 3 − v 4 tidak menjadi geodesic rainbow.
▪ Hal ini kontradiksi dengan asumsi awal.
Karena  tidak  semua  asumsi  awal  itu  terbukti  benar,  maka  hal  ini  dianggap kontradiksi  dengan  asumsi  awal.  Dengan  demikian 𝑠𝑟𝑐(1𝑆𝑝𝑙 − (𝐶 𝑛 )) ≥ 6 . Karena  berdasarkan  konstruksi  pewarnaan  diperoleh 𝑠𝑟𝑐(1𝑆𝑝𝑙 − (𝐶 𝑛 )) ≤ 6, maka 𝑠𝑟𝑐(1𝑆𝑝𝑙 − (𝐶 𝑛 )) = 6 untuk 𝑛 = 10 .

## 3 Kesimpulan
Pada penelitian ini didapatkan hasil strong rainbow connection ( 𝑠𝑟𝑐 ) dari graf 1𝑆𝑝𝑙 − 𝐶 𝑛 untuk 3 ≤ 𝑛 ≤ 10 .  Sehingga  masih  banyak  graf  lain  yang  belum diteliti.
Open  Problem  1.  Bagaimana  hasil strong  rainbow  connection ( 𝑠𝑟𝑐 )  pada  graf 1 𝑆𝑝𝑙 − 𝐶 𝑛 untuk 𝑛 > 10 ?
Open  Problem  2.  Misalkan 𝐺 adalah  sembarang  graf.  Bagaimana  hasil strong rainbow connection ( 𝑠𝑟𝑐 ) pada graf split 𝐺 ?

## 4    Daftar Pustaka
[1] Gary  Chartrand,  dkk.  2008. Rainbow  Connection  in  Graphs .  Mathematica Bohemica 133. Hal: 85-98.
[2] Kiki  A.  S.,  dkk.  2014.  Teori  Graf  dan  Aplikasinya.  Depok:Departemen Matematika FMIPA Universitas Indonesia.
[3] S.K.  Vaidya,  dkk.  2011. Some  New  Odd  Harmonious  Graphs .  International Journal of Mathematics and  Soft Computing 1. Hal: 9-16.