## BILANGAN RAINBOW CONNECTION DARI HASIL OPERASI PENJUMLAHAN DAN PERKALIAN KARTESIUS DUA GRAF

## Fuad Adi Saputra
Mahasiswa Jurusan Matematika UIN Maulana Malik Ibrahim Malang e-mail: tee_fu@yahoo.com

## ABSTRAK
Graf dengan  pewarnaan  sisi  disebut  pelangi  sisi  terhubung,  jika  setiap  titik  pada  graf dihubungkan oleh lintasan yang memiliki sisi-sisi dengan warna yang berbeda. Rainbow connection pada graf yang terhubung, disimbolkan oleh
yaitu bilangan terkecil dari warna yang dibutuhkan untuk membuat graf menjadi pelangi sisi terhubung. Sedangkan graf dengan pewarnaan titik adalah pelangi titik  terhubung,  jika  setiap  titik  pada  graf dihubungkan  oleh  lintasan  yang  memiliki  titik-titik  interior dengan  warna  yang  berbeda. Rainbow  vertex-connection pada  graf yang  terhubung  disimbolkan  oleh yaitu  bilangan  terkecil  dari  warna  yang  dibutuhkan  untuk  membuat  graf menjadi  pelangi  titik terhubung . Penelitian  ini  menganalisis  besarnya  bilangan dan dari  graf  hasil  penjumlahan dan perkalian kartesius dua sebarang graf.
Penjumlahan  dua  graf
dan yang  dinotasikan mempunyai  himpunan  titik dan  himpunan  sisi | .
Bilangan rainbow  connection dari  graf adalah:  1) 1, dan adalah  graf  komplit,  dan  2) 2, atau adalah bukan graf komplit sedangkan  bilangan rainbow  vertex-connection dari graf adalah:
0, d an a dalah graf komplit 1, a tau a dalah bukan graf komplit Graf hasil  kali  kartesius  adalah  graf  yang  dinotasikan dan  mempunyai  titik ,  dan  dua  titik , dan
, dari  graf terhubung  langsung  jika  dan  hanya jika dan
atau
dan
. Bilangan rainbow  connection dari  graf adalah: "# "# $  $ sedangkan  bilangan rainbow  vertex- connection dari graf adalah: "# "# % 1 $  $ 1
Kata kunci: Graf Penjumlahan, Graf Perkalian Kartesius, Rainbow Connection, Rainbow Vertex-Connection

## ABSTRACT
An edge-colored graph is rainbow edge-connected if any two vertices are connected by a path whose  edges  have  distinct  colors.  The  rainbow  connection  of  a  connected  graph ,  denoted  by ,  is the  smallest  number  of  colors  that  are  needed  in  order  to  make rainbow  edge-connected.  A  vertex- colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection of a connected graph , denoted by , is the  smallest  number  of  colors  that  are  needed  in  order  to  make rainbow  vertex-connected.  This research  was  analysis  about  number  of and
from  the  join  and  cartesian  product  of  two graphs.
The join has
and
| . The number of rainbow connection from graph is: 1) 1, and are complete graph, and 2) 2, or are non-complete graph and then the number of rainbow vertex- connection from graph is:
0,
a nd a re complete graph 1, o r ' n on % complete graph The  cartesian  product has ,  and  two  vertices , and , of adjecent if only if either and
or
and
. The number of rainbow connection from graph is: "# "# $  $ and  then  the  number  of rainbow  vertex-connection from  graph is:
"#
"# % 1 $
$ 1
Keywords: Cartesian Product, Join Graph, Rainbow Connection , Rainbow Vertex - Connection

## PENDAHULUAN
Matematika  merupakan  raja  dan  pelayan bagi  disiplin  ilmu  lain  atau  pun  dalam  lini kehidupan.  Teori  graf  merupakan  salah  satu cabang  matematika  yang  penting  dan  banyak manfaatnya karena teori-teorinya dapat diterapkan  untuk  memecahkan  masalah  dalam kehidupan sehari-hari. (Purwanto, 1998:1).
Graf G adalah  pasangan  himpunan  ( V , E ) dengan V adalah  himpunan  tidak  kosong  dari obyek-obyek  yang  disebut  sebagai  titik  dan E adalah  himpunan  (mungkin  kosong)  pasangan tak  berurutan  dari  titik-titik  berbeda  di V yang disebut  sebagai  sisi.  Himpunan  titik  di G dinotasikan  dengan V(G) dan  himpunan  sisi dinotasikan dengan E (G) (Chartrand dan Lesniak, 1986: 4).
Pewarnaan  pada  graf adalah  pemetaan warna-warna ke titik atau sisi dari sedemikian hingga  titik  atau  sisi  yang  terhubung  langsung mempunyai warna-warna yang berbeda.
Dalam  teori  graf  konsep  pewarnaan  terus mengalami  perkembangan,  salah  satunya  adalah tentang rainbow  connection. Rainbow  connection dibagi  menjadi  2  jenis,  yang  pertama  adalah pelangi  sisi  terhubung  ( rainbow  edge-connected ) yang  didefinisikan  sebagai  pewarnaan  sisi  pada graf jika  setiap  titik  pada  graf dihubungkan oleh  lintasan  yang  memiliki  sisi-sisi  dengan warna  yang  berbeda,  sedangkan  yang  kedua adalah  pelangi  titik  terhubung  ( rainbow  vertex- connected ) yang didefinisikan sebagai pewarnaan titik  pada  graf jika  setiap  titik  pada  graf dihubungkan  oleh  lintasan  memiliki  titik-titik interior  dengan  warna  yang  berbeda.  Bilangan rainbow connection pada graf terhubung disimbolkan  oleh yaitu  bilangan  warna terkecil  pada  sisi  yang  dibutuhkan  untuk membuat menjadi pelangi sisi yang terhubung.
Bilangan rainbow  vertex-connection pada  graf terhubung  disimbolkan  oleh yaitu bilangan warna  terkecil  pada  titik  yang dibutuhkan  untuk  membuat menjadi  pelangi titik terhubung (Krivelevich dan Yuster, 2010:1) Jurnal yang ditulis oleh Michael Krivelevich dan Raphael Yuster (2010) menjelaskan mengenai bilangan rainbow connection yang  dibangun  oleh  derajat  terkecil dari  suatu  graf  umum.  Mereka  mengembangkan dari  kajian  yang  ditulis  oleh    Y.  Caro,  A.  Lev,  Y. Roditty,  Z.  Tuza,  dan  R.  Yuster  (2008)  dalam jurnalnya  yang  berjudul On  Rainbow  Connection . Dalam  jurnal On  Rainbow  Connection hasil  dari bilangan rainbow  connection dan masih  dibatasi  oleh  suatu  variabel  yang  belum jelas,  misalkan $ て /* ,  dimana + adalah variabel.  Kemudian  oleh  Krivelevich  dan  Yuster dikembangkan  lagi  dan  berhasil  menentukan nilai variabelnya menjadi $ 20/*
sehingga  batas  nilai + menjadi  lebih  jelas.  Selain itu  juga  dijelaskan  bahwa  bilangan "#
Penelitian yang dilakukan oleh Krivelevich dan Yuster menggunakan objek graf yang umum. Sedangkan  untuk  graf  dari  hasil  operasi  belum diteliti, khususnya pada operasi penjumlahan dan perkalian  kartesius,  sehingga  perlu  dilakukan penelitian lagi untuk objek graf tersebut.

## KAJIAN TEORI

## 1. Graf
Graf G adalah  pasangan  himpunan  ( V , E ) dengan V adalah  himpunan  tidak  kosong  dari obyek-obyek  yang  disebut  sebagai  titik,  dan E adalah  himpunan  (mungkin  kosong)  pasangan tak  berurutan  dari  titik-titik  berbeda  di V yang disebut  sebagai  sisi.  Himpunan  titik  di G dinotasikan  dengan V(G) dan  himpunan  sisi dinotasikan dengan E (G).
2. Adjacent dan Incident Sisi e =  ( u , v) dikatakan  menghubungkan titik u dan v .  Jika e =  ( u , v )  adalah  sisi  di  graf G , maka u dan v disebut  terhubung  langsung ( adjacent ), u dan e serta v dan e disebut  terkait langsung  ( incident ).  Untuk  selanjutnya,  sisi e = ( u , v ) akan ditulis e = uv. Derajat  titik v di graf G , ditulis  deg G ( v ),  adalah  banyaknya  sisi  di G yang terkait  langsung  dengan v (Chartrand  dan Lesniak, 1986:4).
Contoh:
Gambar 2.1 Graf G
Gambar 1. Contoh adjacent dan incident
Dari Gambar 1 titik v 4 dan sisi e 2 , e 3 dan e 4 adalah terkait langsung. Sedangkan titik v 3 dan v 4 adalah terhubung langsung tetapi v 3 dan v 2 tidak.
3. Graf Terhubung Suatu  jalan  ( walk ) u - v pada  graf G adalah barisan  berhingga  (tak  kosong) W : u = u 0 ,  e 1 ,  u 1 , e 2 , . . ., u n-1 , e n , u n = v yang berselang seling antara titik dan sisi, yang dimulai dari titik u dan diakhiri dengan titik v , dengan
i i i u u e 1 − = untuk i = 1, 2, . .
., n adalah  sisi  di G.  u 0 disebut  titik  awal, u n disebut  titik  akhir, u 1 , u 2 ,  ..., u n -1 disebut  titik internal,  dan n menyatakan  panjang  dari W (Chartrand dan Lesniak, 1986:26). Jalan u-v yang  semua  sisinya  berbeda disebut trail u-v. Jalan u - v yang  semua  sisi  dan titiknya berbeda disebut lintasan ( path ) u-v . P : u
4 v 3 v 1 v 2 v e 3 e 2 e 4 e 1
= u 0 ,  e 1 ,  u 1 ,  e 2 ,  .  .  .,  u n-1 ,  e n ,  u n = v, u 0 disebut  titik awal, u n disebut titik akhir. Sedangkan u 1 , u 2 , ..., u n - 1 disebut titik internal, dan n menyatakan panjang dari P. Dengan  demikian,  semua  lintasan  adalah trail. Graf lintasan  dengan titik  dinotasikan dengan , - (Chartrand dan Lesniak, 1986:26).
Contoh:
G:
Gambar 2. Graph Terhubung
Dari graf  di atas v 1 , e 1 , v 2 , e 5 , v 5, e 6 , v 4, e 4 , v 2, e 2 , v 3 adalah trail, sedangkan v 1 , e 1 , v 2 , e 5 , v 5, e 6 , v 4 adalah lintasan.
Misalkan u dan v titik berbeda pada graf G . Maka  titik u dan v dapat  dikatakan  terhubung ( connected ),  jika  terdapat  lintasan u – v di G . Sedangkan  suatu  graf G dapat  dikatakan terhubung  ( connected ),  jika  untuk  setiap  titik u dan v di G terhubung  (Chartrand  dan  Lesniak, 1986:28).
Misalkan u dan v titik berbeda pada graf G, maka  jarak  antara  dua  titik  di adalah  panjang lintasan  terpendek  antara  kedua  titik  tersebut yang  dinotasikan  dengan "./ 0 , . Sedangkan eksentrisitas  titik adalah ' max "./ 0 , : . Radius dari adalah min ': dan diameter dari adalah "#   max ':
(Chartrand dan Lesniak, 1986:29).
4.  Operasi pada Graf Penjumlahan  dua  graf dan yang dinotasikan
mempunyai  himpunan titik dan  himpunan  sisi | (Chartrand dan Lesniak, 1986: 11).
Perhatikan contoh di bawah ini.
G 1 :                G 2 : G:
Gambar 3. Penjumlahan Graf
Hasil  kali  kartesius  adalah  graf  yang dinotasikan dan  mempunyai  titik , dan dua titik , dan , dari  graf terhubung  langsung  jika  dan hanya jika dan atau
dan
(Chartrand  dan  Lesniak,  1986: 11).
Perhatikan contoh berikut, G 1 : G 2 :              G 1 x G 2 :
Gambar 4 . Graf Hasil Kali Kartesius
5. Jenis Graf
a.  Graf  komplit  ( Complete  Graph )  adalah  graf dengan  setiap  pasang  titik  yang  berbeda dihubungkan  langsung  oleh  satu  sisi.  Graf komplit  dengan titik  dinyatakan  dengan K n (Purwanto, 1998:21).
b.  Graf  bipartisi  komplit  ( complete  bipartite graph ) adalah graf bipartisi dengan himpunan partisi X dan Y sehingga masing-masing titik di X dihubungkan dengan masing-masing titik di Y oleh  tepat satu sisi. Jika | X | = m dan | Y |  = n, maka  graf  bipartisi  tersebut  dinyatakan dengan K m,n . (Purwanto, 1998:22). c.  Graf sikel C n adalah graf terhubung n titik yang setiap titiknya berderajat 2. Misal graf sikel C n mempunyai himpunan titik V(C n ) =
, maka graf tersebut
mempunyai himpunan sisi E(C n ) = dimana
untuk
setiap i =1,2,…, n . d.  Graf  roda  adalah  graf  yang  dibentuk  dari operasi  penjumlahan    antara  graf  sikel  ( + - ) dan  graf  komplit  dengan  satu  titik  ( 5 - .  Graf roda  dinotasikan  dengan 6 - dan 3 (Harary, 1969:46)
e.  Graf  kipas  dibentuk  dari  penjumlahan  graf komplit  ( 5 dan  graf  lintasan  ( , - yaitu 8 - 5 , - .  Dengan  demikian  graf    kipas mempunyai  ( 1 titik  dan  ( 2 % 1 )  sisi  ( Gallian, 2007: 16)
f.    Graf  Kipas  Ganda  dibentuk  dari  penjumlahan antara  gabungan  dua  graf  komplit  ( 5 dan graf  lintasan  ( , - yaitu 〰 8 - 25 , - . Dengan  demikian  graf  kipas  mempunyai ( 2 titik dan ( 3 % 1 ) sisi. g.    Graf  tangga  yang  dinotasikan  sebagai 9 - adalah suatu graf yang dibentuk dari operasi hasil  kali  kartesius  antara  graf  lintasan dengan  dua  titik  dan  graf  lintasan  dengan  n titik yaitu 9 - , : , - (Galian, 2007:12)

## 6. Pewarnaan Graf
Pewarnaan  titik  dari  graf G adalah  suatu proses  pemberian  warna  pada  titik-titik  suatu graf  sehingga  tidak  ada  dua  titik  yang  terhubung langsung pada graf tersebut berwarna sama. Graf
} ,..., , { 2 1 n v v v } ,..., , { 2 1 n e e e 1 + = i i i v v e v 1 v 2 v 3 e 1 e 2 e 5 v 5 v 4 e 6 e 3 e 4 u u v v v v v v u u
( u 2 ,v 2 )
( u 1 ,v 2 ) ( u 1 ,v 3 ) ( u 2 ,v 3 ) ( u 1 ,v 1 ) ( u 2 ,v 1 ) v v v u u
G berwarna n jika  terdapat  pewarnaan  dari G yang  menggunakan n warna  (Chartrand  dan Lesniak, 1986:271).
Suatu  pewarnaan  sisi- k untuk  graf G adalah  suatu  penggunaan k warna  untuk mewarnai semua sisi di G sehingga setiap pasang sisi  yang  mempunyai  titik  persekutuan  diberi warna  yang  berbeda.  Jika G mempunyai pewarnaan  sisi- n ,  maka  dikatakan  sisi-sisi  di G diwarnai  dengan n warna . Indeks  kromatik G dinotasikan  dengan
adalah  bilangan n terkecil  sehingga  sisi  di G dapat  diwarna  dengan n warna (Purwanto, 1998:80).
7. Rainbow Connection
Pewarnaan sisi pada graf disebut pelangi sisi  terhubung  ( rainbow  edge-connected) jika setiap titik pada graf dihubungkan oleh lintasan yang  memiliki  sisi-sisi  dengan  warna  yang berbeda. Rainbow  connection pada  graf yang terhubung  ( connected  graph )  disimbolkan  oleh yaitu  bilangan  terkecil  dari  warna  yang dibutuhkan  untuk  membuat  graf  G    menjadi pelangi  sisi  terhubung  ( rainbow  edge-connected) ( Krivelevich dan Yuster, 2010:1). Lintasan  pelangi  ( rainbow  path )  adalah lintasan  antara  dua  titik  sehingga  tidak  ada  dua sisi  pada  lintasan  tersebut  yang  memiliki  warna yang  sama.  Jika  lintasan  pelangi  tersebut  ada  di setiap antara dua titik  maka pewarnaan  tersebut dinamakan pewarnaan pelangi ( rainbow colouring ).  Sedangkan  bilangan  minimum  pada warna  yang  diinginkan  dinamakan  bilangan pelangi  yang  terhubung  ( rainbow  connection number rc(G)). ( L. Sunil Chandran,2011:3). Pewarnaan titik pada graf adalah Pelangi titik  terhubung  ( rainbow  vertex-connected) jika setiap titik pada graf dihubungkan oleh lintasan memiliki  titik-titik  interior  dengan  warna  yang berbeda. Rainbow  vertex-connection pada  graf yang  terhubung  ( connected  graph )  disimbolkan oleh yaitu  bilangan  terkecil  dari  warna yang dibutuhkan untuk membuat graf G  menjadi pelangi titik terhubung ( rainbow vertex- connected) ( Krivelevich dan Yuster, 2010: 2).
Misalkan  graf memiliki titik,  maka $  % 1 .  Kemudian  jika  graf  sikel + - dengan 3 maka $ ; - < .  Sedangkan  jika dihubungkan dengan "# , maka "# dan "#  % 1 ( Krivelevich dan Yuster, 2010:1-2).
1
1 1 2 3 3 3 4 5 5 5 ? ? ? @ @ @ A A A
Gambar 5. Graf Pelangi Sisi Terhubung dan Pelangi Titik Terhubung
Gambar  5  merupakan  contoh  dari  graf pelangi  sisi  terhubung  dan pelangi  titik terhubung dengan 5 warna sisi dan 3 warna titik. Pada  gambar  di  atas  mempunyai  bilangan 5 dan 3 .

## PEMBAHASAN
Dalam pembahasan ini, sebelum mengkaji  inti  permasalahan  yaitu  mengkaji bilangan rainbow  connection dan  bilangan rainbow vertex-connection pada graf hasil operasi penjumlahan  dan  perkalian  kartesius  dua  graf dengan  menggunakan  sebarang  graf,  maka  akan dibahas  terlebih  dahulu
dan
dari jenis graf yang dihasilkan oleh operasi penjumlahan dan perkalian kartesius.
1. Bilangan Rainbow  Connection pada  Jenis Graf Hasil Penjumlahan
Pada graf khusus hasil penjumlahan akan diberikan  5  contoh  graf  yaitu  graf  komplit,  graf bipartisi  komplit,  graf  roda,  graf  kipas,  dan  graf Kipas Ganda.
a. Graf Komplit Tabel 1. Pola Bilangan 5 - dan 5 - No Jenis Graf BCD E BFCD E 1. 5 0 0 2. 5 1 0 3. 5 G 1 0 4. 5 H 1 0 5. 5 I 1 0 6. 5 J 1 0 . 5 - 1 0
Dari  pola  yang  ditunjukan  oleh  bilangan rainbow connection dan bilangan rainbow vertex- connection di  atas  dapat  diperoleh  teorema sebagai berikut:

## Teorema 1
Pada graf komplit 5 - banyak titik 2 , bilangan rainbow  connection 5 - 1, dan  bilangan rainbow vertex-connection 5 - 0 . b.  Graf Bipartisi Komplit Secara  umum  graf 5 -,K dapat  dibentuk menjadi  pelangi  sisi  terhubung  hanya  dengan menggunakan  4  warna.  Hal  ini  dapat  dijelaskan dengan  model  lintasan  antara  2  titik  sebagai berikut:
" "1 "2 " "1 1 3 4 2 "2 "1 1 3 4 2 dan "1 "3 "2 Gambar 6. Model Lintasan Graf Bipartisi 5 K,-
) ( ' G χ

## Teorema 2
Graf  bipartisi  komplit 5 -,K dengan $ # dan , #  L ,  maka  bilangan rainbow  connection pada graf 5 -,K adalah:
M5 -,K N   O #,                  jika        1 2,               jika      2 - # 3,     jika     2 - R # $ 3 -
4,                    jika lainnya bilangan rainbow  vertex-connection pada  graf 5 -,K adalah:
5 -,K 1
Bukti: Graf  bipartisi  komplit 5 -,K terdiri  dari  2  partisi, yaitu : dan U ,  dengan |:|   # dan |U| . Misalkan
V :, " 1 , 2 , . . . , # dan
V U, " 1 , 2 , … , .  Maka  setiap  dua  titik V dan setiap dua titik V tidak terhubung langsung, akan  tetapi  setiap  titik V dengan V akan dihubungkan  dengan  satu  sisi.  Terdapat  4  kasus, yaitu:
(i) jika 1 , maka M5 ,K N   # . Andaikan M5 ,K N R # ,  maka  ada  dua  sisi di 5 ,K yang  berwarna  sama.  Misal V , dan M X , N dengan " Y Z . Akibatnya lintasan V % X bukan lintasan pelangi karena hanya ada 1 warna.
Jadi 5 ,K bukan pelangi sisi yang terhubung, jadi M5 ,K N  # . Karena  pewarnaan  sisi  dengan # warna menghasilkan 5 ,K graf  pelangi  sisi,  maka M5 ,K N $ # . Disimpulkan M5 ,K N   #.
(ii) M5 -,K N 2 jika 2 - # . Akan dibuktikan jika 2 - # , maka M5 -,K N 2 , d eg V dan d eg V #
Jika M5 -,K N 2 maka  setiap  dua  titik, maksimal  ada  lintasan  dengan  2  warna  sisi yang  berbeda.  Untuk  itu  jika  setiap  lintasan V % X dan setiap lintasan V % X terbentuk lintasan  pelangi  maka  susunan  warna  yang dikenakan  pada  sisi  yang  terkait  langsung pada V berbeda dengan X , begitu juga pada V berbeda  dengan X .  Selanjutnya  karena d eg V $ d eg V # , maka jika setiap  susunan  warna  yang  dikenakan  pada sisi  yang  terkait  langsung  dengan V berbeda, maka susunan warna yang dikenakan  pada  sisi  yang  terkait  langsung dengan  setiap V juga  berbeda.  Sehingga cukup  dianalisis  susunan  warna  pada  sisi yang terkait langsung dengan titik V :, " 1 , 2 , … , # . Diketahui M5 -,K N 2 dan d eg V ,  jadi dari  2  warna  tersebut  akan  disusun  ke- tempat dengan perulangan, sehingga diperoleh  banyaknya  susunan 2 2
2 G …   2 - 2 - . Kemudian
susunan tersebut diberikan pada setiap titik V dan X dengan " Y Z .  Jika  banyaknya  susunan sebanyak 2 - lebih  banyak  dari  banyaknya titik V yang  sebanyak # ,  maka  setiap V mempunyai susunan warna sisi yang terkait langsung  berbeda  dengan X .  Sehingga lintasan V % X akan  membentuk  lintasan pelangi.  Jadi    terbukti  jika 2 - # maka M5 -,K N 2 .
(iii) Jika M5 -,K N 3 jika 2 - $ # $ 3 - Akan dibuktikan jika 2 - $ # maka
M5 -,K N  3 dan jika # $ 3 - maka M5 -,K N 3 . Ambil M5 -,K N 2 , jika 2 - $ # maka akan dibuktikan  ada  dua  titik  yang  semua lintasannya  mempunyai  warna  sisi  yang sama.  Banyak  susunan  warna 2 - ,  artinya , , … . , [ susunan  warna  sisi  yang terkait  langsung  berbeda.  Karena 2 - $ # maka  ada  titik
[ \] yang  mempunyai susunan  warna  yang  sama  dengan ^ , dengan 1 $  $ # % 2 - dan 1 $ _ $ 2 - . Misalkan  ada  fungsi : M5 -,K N ` 1,
2 , maka [ \] , V
^ , V , sehingga lintasan ^ % [ \] tidak  membentuk lintasan  pelangi,  karena  semua  lintasannya pasti  mempunyai  warna  sisi  yang  sama. Sehingga  terbukti  jika 2 - $ # maka M5 -,K N  3 . Sekarang M5 -,K N 3 dan d eg V , jadi dari  3  warna  tersebut  akan  disusun  ke- tempat dengan perulangan, sehingga diperoleh  banyaknya  susunan 3 3 3 G …   3 - 3 - .
Kemudian susunan tersebut diberikan pada setiap titik V dan X dengan " Y Z. Jika  banyaknya  susunan sebanyak 3 - lebih  banyak  dari  banyaknya titik V yang  sebanyak # ,  maka  setiap V mempunyai susunan warna sisi yang terkait langsung  berbeda  dengan X .  Sehingga lintasan V % X akan  membentuk  lintasan pelangi.  Jadi  terbukti  jika # $ 3 - maka M5 -,K N 3 . (iv) M5 -,K N 4 ,  jika lainnya Jika sudah tidak memenuhi semua ketentuan  di  atas,  untuk  membentuk graf 5 K,- menjadi  pelangi  sisi  terhubung, maka  graf 5 K,- dapat  diwarnai  minimal mengunakan  4  warna.  Misalkan  ada  fungsi pewarnaan sisi : M5 -,K N ` 1, 2 , 3 , 4 maka: M V , X N 1 , " Y Z 'a "   aZ"b, Z aZ"b, M V , X N 3 , " Y Z 'a "   a'c, Z aZ"b,
M V , X N 2 , " Y Z 'a "   aZ"b, Z
a'c,
M V , X N 4 , " Y Z 'a "   a'c, Z a'c , dengan  pewarnaan  di  atas  maka  setiap  dua titik pada graf 5 K,- terdapat lintasan dengan warna sisi yang berbeda, sehingga graf 5 K,- akan membentuk graf pelangi sisi terhubung,  jadi  dengan  demikian  terbukti M5 K,- N 4 .
(v) M5 K,- N 1 Akan dibuktikan M5 K,- N  1 dan
M5 K,- N $ 1 .
Diketahui
"#M5 K,- N 2 , sehingga M5 K,- N  2 % 1 1 .
Untuk  membuktikan M5 K,- N $ 1, maka akan  dibuktikan  bahwa  dengan  1  warna titik,  dapat  membentuk  pelangi  titik  yang terhubung,  artinya  setiap  dua  titik  terdapat lintasan  dengan  warna  titik  interior  yang berbeda. Ambil M5 K,- N 1 , misalkan ada fungsi  pewarnaan : M5 -,K N ` 1 maka:
V 1 , dan V 1 , sehingga  setiap lintasan V % X akan  melewati  titik  interior
V dimana
V 1 , sedangkan  setiap lintasan V % X akan  melewati  titik  interior
V dimana V 1 ,  dengan  demikian setiap  dua  titik  terdapat  lintasan  dengan warna  titik  interior  yang  berbeda.  Jadi terbukti M5 K,- N $ 1 . Karena M5 K,- N  1 dan M5 K,- N $ 1 ,  maka M5 K,- N 1 . c. Graf Roda Secara  umum  graf 6 - dapat  dibentuk menjadi  graf  pewarnaan  sisi  yang  terhubung, dengan  warna  sisi  minimal  3,  dan  juga  graf 6 - dapat  dibentuk  menjadi  graf  pewarnaan  titik yang  terhubung,  dengan  warna  titik  minimal  1, yang  ditampilkan  dalam  model  pewarnaan berikut:
1 1 %1 5 4 3 2 1 2 1 1 2 2 3 1 ? ? ? ? ? ? ? 3 3 3 3 3 1 d E :
Gambar 7. Graf roda 6 -
Teorema 3 Graf adalah  graf  roda 6 - dengan L ,  maka bilangan rainbow connection pada graf adalah:
6
- e 1,                         jika    3
2,                jika 4 $  $ 6 3,                         jika   7
bilangan rainbow  vertex-connection pada  graf 6 - adalah:
6 -
1,         jika   4
Bukti: Graf  roda 6 - dengan 3 adalah  graf  yang terbentuk  dari  operasi  penjumlahan  antara  graf sikel ( + - ) dan graf komplit dengan satu titik ( 5 .
Misalkan V + - , " 1 , 2 , … , , maka -\ 1 , dan 5 , serta  untuk  semua V terhubung langsung dengan .
(i) Jika 3 ,  akan  dibuktikan 6 G adalah  graf
5 H .
Untuk  semua , , G + G terhubung langsung  dengan , sehingga  diperoleh d eg d eg d eg G d eg 3 . Karena  graf 6 G dengan  4  titik  beraturan % 3 maka 6 G adalah  graf  komplit,  jadi  terbukti dengan 3 maka 6 G 1 . (ii) Jika 4 $  $ 6 maka 6 - 2 Akan dibuktikan 6 - 2 dan 6 - $ 2 Graf 6 - dengan 4 $  $ 6 bukan merupakan graf komplit, karena d eg V 3 sedangkan  jumlah  titiknya
5 $ |6 - | $ 7, sehingga 2 . Kemudian untuk membuktikan $ 2 maka akan
dibuktikan  bahwa  dengan  2  warna  dapat membentuk 6 - menjadi  pelangi  sisi  yang terhubung, sehingga setiap dua titik terdapat  lintasan  dengan  warna  sisi  yang berbeda.  Fungsi  pewarnaan  sisi : 6 - ` 1, 2 yang  didefinisikan  oleh
V , 1 jika " ganjil, V , 2 jika " genap,
V , V\ 1 1 jika " ganjil, V , V\ 1 2 jika " genap. Setiap  lintasan V % atau % V hanya terdapat satu  warna sisi. Kemudian lintasan V % X , jika " genap dan V dan Z ganjil pasti berbentuk lintasan pelangi 2 warna. Sedangkan  untuk  lintasan V % X dengan " dan Z sama-sama  genap  atau " dan Z sama- sama ganjil. Jika V % V\ 2 maka membentuk lintasan  pelangi  yang  sisi-sinya + - . Tetapi jika lintasan V % V\h , dengan 4 $  $  % 2
maka 4 , karena 6 diperoleh
4 $  $ 6 %
2 . Untuk " 1 , dengan  lintasan % I ,  maka  dapat  dibentuk  lintasan pelangi  melewati  titik J ,  sedangkan  untuk
" 2 dengan  lintasan % J ,  maka  dapat dibentuk  lintasan  pelangi  melewati  titik , terbukti  setiap  dua  titik  terdapat  lintasan dengan  warna  sisi  yang  berbeda,  sehingga diperoleh $ 2 .  Jadi  terbukti  untuk 4 $  $ 6 maka
2 .
(iii) Jika 7 maka 3 Akan dibuktikan 3 dan $ 3 . Dibuktikan $ 3 maka akan
dibuktikan  bahwa  dengan  3  warna  dapat membentuk 6 - menjadi  pelangi  sisi  yang terhubung, sehingga setiap dua titik terdapat  lintasan  dengan  warna  sisi  yang berbeda. Jika fungsi pewarnaan sisi : 6 - ` 1, 2 , 3 yang  didefinisikan  oleh V ,
1 jika " ganjil, V ,
2 jika " genap,  dan i 3 , ji  + - maka akan  membentuk  pelangi  sisi  terhubung, sehingga 6 - $ 3 . Selanjutnya dibuktikan 3 , dari hasil di  atas  didapat 6 - bukan  graf  komplit sehingga 2 . Ambil 2
Misalkan  fungsi  pewarnaan  sisi : 6 k ` 1, 2 didefinisikan , 1 , maka H , 2 dan I , 2 , karena  tidak mungkin menggunakan lintasan sisi + - yang panjangnya  3.  Kemudian  jika
V , V\ 1
1 dengan " ganjil,
V , V\ 1 2 dengan " genap,  maka -l 1 , 1 membentuk lintasan  pelangi,  karena  panjang  lintasan dengan sisi + - sama dengan 2 dan warnanya berbeda.  Tetapi  jika G , 1 , lintasan G % -l 1 warnanya  akan  sama  dan  kalau lintasannya  menggunakan  sisi + k juga  tidak mungkin  karena  panjangnya 3,  jadi haruslah G , 2 .  Selanjutnya , harus  sama  dengan  1,  karena I , 2 , akan  tetapi  pewarnaan  demikian  akan membuat  antara  titik dan -l 1 semua lintasannya  akan  mempunyai  warna  yang sama,  sehingga  haruslah , 3 ,  hal tersebut  berlaku  jika 7 karena  lintasan % -l 1 minimal  mempunyai  panjang  3, sehingga 6 - 3. Karena 6 - 3 dan 6 - $ 3 maka  terbukti 6 - 3 , dengan 7 .
(iv) Jjika 4 maka 6 - 1
Akan dibuktikan
6 - 1 dan
6 - $ 1 . Diketahui "#6 - 2 , sehingga 6 - 2 % 1 1 . Untuk  membuktikan 6 - $ 1 ,  maka akan  dibuktikan  bahwa  dengan  1  warna titik,  dapat  membentuk  pelangi  titik  yang terhubung,  artinya  setiap  dua  titik  terdapat lintasan  dengan  warna  titik  interior  yang berbeda.  Ambil 6 - 1 ,  misalkan  ada fungsi  pewarnaan : M5 -,K N ` 1 maka: 1 ,  sehingga  setiap  lintasan V % X akan  melewati  titik  interior dimana 1 ,  sedangkan  setiap  lintasan V % tidak  ada  titik  interior  karena  terhubung langsung,  dengan  demikian  setiap  dua  titik terdapat lintasan dengan warna titik interior yang  berbeda.  Jadi  terbukti 6 - $ 1 .
Karena 6 - 1 dan 6 - $ 1 ,  maka
6 -
1 . d. Graf Kipas
Secara  umum  graf 8 - dapat  dibentuk menjadi  graf  pewarnaan  sisi  yang  terhubung, dengan  warna  sisi  minimal  3,  dan  juga  graf 8 - dapat  dibentuk  menjadi  graf  pewarnaan  titik yang  terhubung,  dengan  warna  titik  minimal  1, yang  ditampilkan  dalam  model  pewarnaan berikut:
1 1 2 1 2 3 4 %1 1 2 2 3 ? ? ? ? ? ? 3 3 3 ? 1 m E : Gambar 8. Graf Kipas 8 -

## Teorema 4
Graf  kipas 8 - dengan L ,  maka  bilangan rainbow connection pada graf 8 - adalah:
8 - e 1,                        Z"n    2 2,                Z"n 3 $  $ 6 3,                         Z"n   7
bilangan rainbow  vertex-connection pada  graf 8 - adalah:
8 -
1,       Z"n   2
Bukti: Graf  kipas 8 - dibentuk  dari  penjumlahan  graf komplit  ( 5 dan  graf  lintasan  ( , - yaitu 8 - 5 , - .  Dengan  demikian  graf  kipas mempunyai  ( 1 titik  dan  ( 2 % 1 )  sisi. Misalkan V , - , " 1 , 2 , … , , dan 5 , serta untuk semua V terhubung langsung dengan
.
(i) Jika 2 ,  akan  dibuktikan 8 adalah  graf 5 G .
Untuk semua , ,
terhubung langsung  dengan , sehingga  diperoleh d eg d eg d eg
2 . Karena graf 8 dengan  3  titik  beraturan % 2 maka 8 adalah  graf  komplit,  jadi  terbukti  dengan
2 maka 1 . (ii) Jika 3 $  $ 6 maka 2 Akan dibuktikan 2 dan $ 2 . Graf 8 - dengan 4 $  $ 6 bukan merupakan graf  komplit,  karena d eg V $ 3 sedangkan jumlah titiknya 4 $ |8 - | $ 7 , sehingga 2 .  Kemudian  untuk  membuktikan $ 2 maka  akan  dibuktikan  bahwa dengan  2  warna  dapat  membentuk 8 - menjadi  pelangi  sisi  yang  terhubung, sehingga  setiap  dua  titik  terdapat  lintasan dengan  warna  sisi  yang  berbeda.  Fungsi
pewarnaan sisi : 8 - ` 1, 2
yang didefinisikan  oleh
V , 1 jika 1 $ " $ o - p, V , 2
jika o - p $ " $ ,
V , V\ 1 1 jika " ganjil, V , V\ 1 2 jika " genap.
Setiap  lintasan V % atau % V hanya terdapat satu  warna sisi. Kemudian lintasan
V % X ,  dengan 1 $ " $ ; - < dan ; - < $ Z $ pasti  berbentuk  lintasan  pelangi  2  warna. Sedangkan  untuk  lintasan V % X dengan " dan Z sama-sama 1 $ " $ ; - < atau  dengan
" dan Z sama-sama ; - < $ " $ .  Lintasan terpanjang  adalah % h dengan ; - < , karena $ 6 maka  lintasan  terpanjangnya % G dan H % J maka  membentuk lintasan  pelangi  2  warna  yang  sisi-sinya anggota , - , sehingga terbukti setiap dua titik terdapat  lintasan  dengan  warna  sisi  yang berbeda,  sehingga  diperoleh $ 2 .  Jadi terbukti untuk 3 $  $ 6 maka 2 . (iii) Jika 7 maka 3 Akan dibuktikan 3 dan $ 3 .
Dibuktikan $ 3 maka akan dibuktikan  bahwa  dengan  3  warna  dapat membentuk 8 - menjadi  pelangi  sisi  yang terhubung, sehingga setiap dua titik terdapat  lintasan  dengan  warna  sisi  yang berbeda. Jika fungsi pewarnaan
sisi
: 8 - ` 1, 2 , 3 yang  didefinisikan  oleh
V ,
1
jika " ganjil, V , 2 jika " genap,  dan i 3 , ji  , - maka akan  membentuk  pelangi  sisi  terhubung, sehingga 8 - $ 3 . Selanjutnya dibuktikan 8 - 3 , dari hasil di  atas  didapat
8 - bukan  graf  komplit sehingga 8 - 2. Ambil 8 - 2
Misalkan  fungsi  pewarnaan  sisi : 8 - ` 1, 2 didefinisikan , 1 , maka \h , 2 , dengan 3 $  $  % 1 karena tidak  mungkin  menggunakan  lintasan  sisi
, - yang  panjangnya 3.  Sedangkan  jika
V , V\ 1 1 dengan " ganjil, V , V\ 1 2 dengan " genap, maka , G , 1 membentuk  lintasan  pelangi, karena panjang lintasan dengan sisi , - sama dengan 2 dan warnanya berbeda.
Pewarnaan  demikian  akan  membuat  antara titik \h dengan 3 dan \h dengan
% 1 semua lintasannya akan mempunyai  warna  yang  sama,  karena
H , - , 2 dan  lintasan  dengan sisi , - dengan 7 panjangnya  lebih  dari sama  dengan  3,    maka  terbukti 8 - 3. Karena 8 - 3 dan 8 - $ 3 maka terbukti 8 - 3 , dengan 7 .
(iv) Jika 2 maka 8 - 1
Akan dibuktikan 8 - 1 dan
8 - $ 1 . Diketahui "#8 - 2 , sehingga 8 - 2 % 1 1 . Untuk  membuktikan 8 - $ 1 ,  maka akan  dibuktikan  bahwa  dengan  1  warna titik,  dapat  membentuk  pelangi  titik  yang terhubung,  artinya  setiap  dua  titik  terdapat lintasan  dengan  warna  titik  interior  yang berbeda.  Ambil 8 - 1 , misalkan  ada fungsi  pewarnaan : 8 - ` 1 maka: 1 ,  sehingga  setiap  lintasan V % X akan  melewati  titik  interior dimana
1 ,  sedangkan  setiap  lintasan V %
tidak  ada  titik  interior  karena  terhubung langsung,  dengan  demikian  setiap  dua  titik terdapat lintasan dengan warna titik interior yang  berbeda.  Jadi  terbukti 8 - $ 1 . Karena 8 - 1 dan 8 - $ 1 ,  maka
8 - 1 .
e. Graf Kipas Ganda Secara  umum  graf 8 - dapat  dibentuk menjadi  graf  pewarnaan  sisi  yang  terhubung, dengan  warna  sisi  minimal  3,  dan  juga  graf 8 - dapat  dibentuk  menjadi  graf  pewarnaan  titik yang  terhubung,  dengan  warna  titik  minimal  1, yang  ditampilkan  dalam  model  pewarnaan berikut:
1 2 1 3 4 6 5 1 2 1 1 2 3 3 3 2 2 2 3 3 3 qm E : 2 2 3 3 3 3 1 1 1 2 2 2 2 2 7 8 9 10 %1 2 2 2 2 2 2
Gambar 9. Graf Kipas Ganda 8 -
Teorema 5 Graf  kipas  ganda 8 - dengan  jumlah  titik 2 , maka  bilangan rainbow  connection pada  graf 8 - adalah:
8 - t2, $ 12
3, 13 bilangan rainbow vertex-connection pada graf 8 - adalah:
8 - 1
Bukti:
Graf  kipas  ganda  dibentuk  dari  penjumlahan antara gabungan dua graf komplit ( 25 dan graf lintasan  ( , - yaitu 8 - 2 5 , - .  Dengan demikian graf kipas mempunyai ( 2 titik dan ( 3 % 1 ) sisi.
(i) 8 - 2 jika 2 $  $ 1 2 .
Akan dibuktikan 8 - 2 , dan
8 - $ 2 . Diketahui "# 8 - 2 , karena "# maka diperoleh 8 - 2 . Misalkan V , - dengan
2 $  $ 1 2 , " 1 , 2 , … , dan V 2 5 dengan " 1 , 2 , terdapat  fungsi  pewarnaan  sisi : 8 - ` 1, 2 yang  didefinisikan  oleh V , 1
jika 1 $ " $ ; - < ,
V ,
2 jika o - p R " $ 1 2 , V , V\ 1
1 jika " ganjil, V , V\ 1
2 jika " genap,  serta V , 1 jika 1 $ " $ ; - H < dan ; - < R " $ ; Gu- H < ,  kemudian
V , 2 jika
o - H p R " $ ; - < dan
; Gu- H < R " $ ,  maka  akan  membentuk  graf 8 - menjadi graf pelangi sisi yang terhubung dimana  setiap  dua  titik  terdapat  lintasan dengan  warna  sisi  yang  berbeda.  Hal  ini membuktikan  bahwa 8 - $ 2 ,  jadi diperoleh dengan 2 $  $ 1 2 maka 8 - 2 .
(ii)
8 -
3 jika 1 3 .
Akan dibuktikan 8 - 3 , dan 8 - $ 3 . Pertama  dibuktikan 8 - 3, ambil
8 - 2 , maka dibuktikan dengan menggunakan  2  warna  sisi  akan  ada  2  titik yang  semua  lintasannya  memiliki  warna yang  sama.  Misalkan V , - dengan 1 3 , " 1 , 2 , … , dan V 2 5 dengan " 1 , 2 ,  terdapat  fungsi  pewarnaan  sisi : 8 - ` 1, 2 , akan  dibentuk  setiap  dua titik  dihubungkan  oleh  lintasan  pelangi.
Misalkan lintasan V % X , karena
V , V\ 1 1 jika " ganjil, V , V\ 1 2 jika " genap,
maka
Z  " 3 . Jika
V , 1 agar  lintasan V % X terbentuk lintasan pelangi maka 〳 M X , N 2 . Kemudian  lintasan V % X\ 1 , V % X\ 2 , V % X\ 3 maka haruslah M X\ 1 , N M X\ , N   M X\ 3 , N 2 , kemudian untuk  lintasan X % X\ 3 ,  karena M X , N M X\ 3 , N 2 dan  panjang  lintasan  dengan sisi , - sama dengan 3 pasti lintasan tersebut memiliki  warna  yang  sama,  sehingga M X , N 1 dan
M X\ 3 , N 2 . Selanjutnya  lintasan X % X\ 4 , X % X\ 5 ,
X % X\ 6 maka haruslah M X\ 4 , N M X\ 5 , N   M X\ 6 , N 2 . Pewarnaan demikian akan membuat lintasan X\ 3 % X\ 6 memiliki  warna  sisi  yang  sama,  sehingga dengan  2  warna  sisi  saja  maksimal  cukup untuk titik X sampai X\ 5 . Begitu juga untuk
V sampai V\ 5 . Sehingga dengan 2 warna sisi
berlaku  untuk  12  titik,  sedangkan  untuk 1 3 tidak bisa membuat 8 - menjadi graf pelangi  sisi  yang  terhubung.  Jadi  terbukti 8 - 3 .
Selanjutnya  jika  fungsi  pewarnaan  sisi : 8 - ` 1, 2 , 3 yang  didefinisikan  oleh V , 1 jika " ganjil, V , 2 jika " genap, V , 2 dan i 3 , ji  , - maka akan membentuk pelangi sisi terhubung, sehingga 8 - $ 3. Terbukti  dengan 1 3 maka 8 - 3 .
(iii) Jika 2 maka 8 - 1 Akan dibuktikan 8 - 1 dan 8 - $ 1 . Diketahui "#8 - 2 , sehingga 8 - 2 % 1 1 . Untuk  membuktikan 8 - $ 1 ,  maka akan dibuktikan bahwa dengan 1 warna titik, dapat membentuk pelangi titik yang terhubung,  artinya  setiap  dua  titik  terdapat lintasan  dengan  warna  titik  interior  yang berbeda.  Ambil 8 - 1 , misalkan  ada fungsi  pewarnaan : 8 - ` 1 maka: 1 , sehingga  setiap  lintasan V % X akan  melewati  titik  interior dimana
1 ,  untuk  lintasan % jika V
1 ,  maka  akan  melewati  titik  interior V dimana V 1 ,  sedangkan  setiap lintasan V % dan V % tidak  ada  titik interior  karena  terhubung  langsung,  dengan demikian  setiap  dua  titik  terdapat  lintasan dengan  warna  titik  interior  yang  berbeda.
Jadi
terbukti
8 - $ 1. Karena
8 - 1 dan 8 - $ 1 , maka 8 - 1 .
2. Bilangan Rainbow  Connection pada  Jenis Graf Hasil Perkalian Kartesius
Pada graf khusus hasil perkalian kartesius  akan  ditampilkan    1  contoh    graf  yaitu graf  tangga.  Graf  tangga  dibentuk  dari  perkalian kartesius graf lintasan dengan 2 titik ( , ) dengan graf lintasan dengan n titik ( , - . Tabel 2. Pola bilangan 9 - dan 9 - No Jenis Graf BCv E BFCv E 1. 9 2 1 2. 9 G 3 2 3. 9 H 4 3 4. 9 I 5 4 5. 9 J 6 5
.
9 - % 1
Teorema 6 Pada  graf  tangga 9 - dengan  banyak  titik 2, bilangan rainbow  connection 9 - , dan
bilangan rainbow  vertex-connection 9 - % 1 .

## Bukti:
Graf  tangga  yang  dinotasikan  sebagai 9 - adalah suatu  graf  yang  dibentuk  dari  operasi  hasil  kali kartesius  antara  graf  lintasan  dengan  dua  titik dan  graf  lintasan  dengan  n  titik  yaitu 9 - , : , - ,  dengan V , - , "   1,2, … , dan V , , "   1,2 .
(i) Akan dibuktikan
9 - , dan 9 - % 1 . Diketahui  graf  tangga 9 - memiliki  panjang diameter "#9 - . Karena "# dan "# %
1, maka  terbukti dan
% 1 . (ii) Akan dibuktikan 9 - $ , dan 9 - $  % 1 . Misalkan graf 9 - dibagi 2 himpunan titik : dan U .  Di  mana V , : dan V , U, terdapat  fungsi  pewarnaan sisi : 9 G ` 1,2, … , , maka: M V , , V\ , N   ", dengan " 1,2, … ,  % 1 , M V , , V , N M V , , V\ , N   ", dengan "   1,2, … ,  % 1 . Pewarnaan  sisi  demikian  akan  membuat graf 9 - menjadi  pelangi  sisi  yang terhubung, sehingga 9 - $ . Selanjutnya  misal  fungsi  pewarnaan  titik w : 9 J ` 1,2, … ,  % 1, maka: w V , " , dengan "   1,2, … ,  % 1 , w V , " , dengan "   1,2, … ,  % 1 ,
w - , w - , 1 Pewarnaan  titik  demikian  akan  membuat graf 9 - menjadi  pelangi  titik  yang terhubung, sehingga 9 - $  % 1 . Dari  (i)  dan  (ii)  terbukti 9 -
dan
9 - % 1 .
3. Bilangan Rainbow Connection pada Sebarang Graf
Pada  pembahasan  ini,  telah  didapat model  atau  teorema  dari  bilangan rainbow connection dan bilangan rainbow vertex- connection pada jenis graf dari hasil penjumlahan dan perkalian kartesius dua graf. Dengan berpikir induktif,  maka  dari  pola-pola  tersebut  dapat disimpulkan dan pada  sebarang graf.  Graf  disini  merupakan  sebarang  graf berhingga dan jika dioperasikan akan menghasilkan  graf  yang  terhubung.  Kemudian dengan berpikir deduktif maka pola-pola bilangan rainbow  connection dan  bilangan rainbow  vertex-connection pada  sebarang  graf tersebut dapat dibuktikan kebenarannya.
a. Bilangan Rainbow  Connection pada  Graf Hasil Penjumlahan
Untuk  menentukan  bilangan rainbow connection pada  graf  hasil  penjumlahan  dengan obyek sebarang graf yaitu dengan cara menganalisis  bilangan rainbow  connection dari jenis  graf  hasil  penjumlahan  dua  graf  yang  telah ditampilkan di atas. Terdapat 5 contoh graf, yaitu graf komplit, graf bipartisi komplit, graf roda, graf kipas, dan graf kipas ganda.
Dari  kelima  graf  tersebut  dibagi menjadi  dua  bagian.  Bagian  pertama  adalah  graf hasil  dari  penjumlahan  dua  graf  komplit, sedangkan  yang  kedua  adalah  graf  hasil  dari penjumlahan  dua  bukan  graf    komplit.  Untuk bagian pertama yaitu graf hasil dari penjumlahan dua  graf  komplit  dicontohkan  oleh  graf  komplit 5 - ,  sedangkan  bagian  kedua  yaitu  graf  hasil  dari penjumlahan dua bukan graf komplit dicontohkan oleh graf bipartisi komplit 5 K,- , graf roda 6 - , graf kipas 8 - dan graf kipas ganda 8 - . Graf  komplit 5 - bilangan 5 - 1 , sedangkan 5 - 0 .  Pada  graf  bipartisi 5 K,- komplit  bilangan M5 K,- N  2 dan M5 K,- N 1. Untuk  graf  roda 6 - bilangan 6 - 2 dan bilangan 6 - 1 .  Graf  kipas 8 - bilangan 8 - 2 dan 8 - 1 .  Sedangkan  pada graf  kipas  ganda 8 - bilangan 8 - 2 dan 8 - 1 . Melihat  hasil  di  atas  diperoleh  suatu teorema  bilangan rainbow  connection dan bilangan rainbow  vertex-connection pada  graf hasil dari penjumlahan dua sebarang graf sebagai berikut:

## Teorema 7
Misalkan  graf adalah  graf  hasil  penjumlahan sebarang  graf dan  sebarang  graf ,  maka bilangan rainbow connection dari graf adalah:
1, dan adalah graf komplit
2, atau adalah bukan graf komplit sedangkan  bilangan rainbow  vertex-connection dari graf adalah:
e 0, dan adalah graf komplit 1, atau adalah bukan graf komplit Bukti:
Penjumlahan dua graf dan yang dinotasikan mempunyai himpunan titik dan himpunan sisi | .
[1] Jika dan adalah graf komplit. Misalkan 5 K dan 5 - maka banyak titik  dari  graf adalah #  . Anggap dan , sebelum dioperasikan
deg   # % 1 ,  sedangkan deg    % 1 . Kemudian dioperasikan penjumlahan  antara dan , diperoleh
setiap  titik  pada  graf terhubung  langsung dengan setiap titik pada , | . Sehingga
derajat  setiap  titik bertambah  sebanyak menjadi deg   #   % 1 dan  derajat setiap titik bertambah sebanyak # menjadi deg   #   % 1. Artinya  setiap  titik , beraturan- #   % 1 sehingga graf adalah graf 5 K\- . Terbukti bahwa graf
dari penjumlahan dua graf komplit mempunyai bilangan rainbow connection dan bilangan rainbow vertex-connection
berturut-turut sebesar 1 dan 0.
[2] Jika atau adalah  graf  bukan  komplit dan . Misalkan V , X , dengan ", Z
1,2, … , , serta
 ,  , dengan , .
1,2, … , # maka , , ,  . Akan dibuktikan "#   2 , ada 3 kemungkinan: 1) graf  komplit  dan bukan  graf komplit. Jika graf komplit maka "# 1 . bukan graf komplit maka "# n  0. Misalkan  lintasan  %  adalah lintasan  dengan  panjang  kurang  dari sama  dengan n .  Karena  terhubung langsung  dengan V dan  juga terhubung  langsung  dengan V . Maka lintasan  %  dapat  dibuat  melewati
V , sehingga panjang lintasannya menjadi 2. Dengan demikian "#   2 .
2) bukan  graf  komplit  dan graf
komplit.
Jika graf komplit maka "# 1. bukan graf komplit maka "# b  0. Misalkan  lintasan V % X adalah lintasan  dengan  panjang  kurang  dari sama  dengan b .  Karena V terhubung langsung  dengan  dan X juga
terhubung  langsung  dengan  .  Maka lintasan V % X dapat dibuat melewati  , sehingga  panjang  lintasannya  menjadi  2. Dengan demikian "#   2 .
3) bukan graf komplit dan bukan graf komplit.
bukan  graf  komplit  maka "# b
0 .  Misalkan  lintasan V % X adalah  lintasan dengan  panjang  kurang  dari  sama  dengan b . Karena V terhubung langsung dengan  dan X juga  terhubung  langsung  dengan  .  Maka lintasan V % X dapat  dibuat  melewati  , sehingga panjang lintasannya menjadi 2. bukan graf komplit maka "# n 0. Misalkan  lintasan  %  adalah  lintasan dengan  panjang  kurang  dari  sama  dengan n. Karena  terhubung langsung dengan V dan  juga terhubung langsung dengan V . Maka lintasan  %  dapat  dibuat  melewati V ,
sehingga  panjang  lintasannya  menjadi  2. Dengan demikian "#   2 .
Dari  3  kasus  di  atas  disimpulkan  jika kemudian atau adalah bukan  graf  komplit  maka "#    2. Karena "# maka  terbukti
2 .
Selanjutnya dibuktikan 1 . Akan dibuktikan 8 - 1 dan
8 - $ 1 . Diketahui "#   2 , sehingga 2 % 1   1 . Untuk  membuktikan $ 1 ,  maka  akan dibuktikan  bahwa  dengan  1  warna  titik, dapat membentuk pelangi titik yang terhubung,  artinya  setiap  dua  titik  terdapat lintasan  dengan  warna  titik  interior  yang berbeda.  Ambil 1, misalkan  ada fungsi pewarnaan
:  ` 1 maka:
V 1 ,  sehingga  setiap  lintasan  %  akan  melewati  titik  interior V dimana 1 , untuk lintasan
V % X jika  1, maka  akan  melewati  titik  interior V dimana  1, sedangkan  setiap lintasan  % V tidak ada titik interior karena terhubung langsung, dengan demikian setiap dua titik terdapat lintasan dengan warna titik interior yang berbeda. Jadi terbukti $ 1. Karena 1 dan
$ 1, maka 1 .
b. Bilangan Rainbow  Connection pada  Graf Hasil Perkalian Kartesius
Untuk  menentukan  bilangan rainbow connection graf  hasil  perkalian  kartesius  dengan sebarang  graf  yaitu  dengan  cara  menganalisis bilangan rainbow  connection dari  graf  khusus hasil  perkalian  kartesius  dua  graf  yang  dengan contoh graf tangga 9 - . Dari hasil pembahasan mengenai bilangan rainbow  connection dan  bilangan rainbow  vertex-connection pada  graf  tangga 9 - , diperoleh  bilangan
dan  bilangan % 1 . Kedua pola tersebut dipengaruhi oleh bilangan
dan dari graf sebelum dioperasikan  oleh  perkalian  kartesius,  yaitu , dengan , - .
Untuk , didapat dari penjumlahan antara
pada , dengan pada , - yang  masing  besarnya 1 dan % 1 , dimana  penjumlahan  kedua  akan  menghasilkan 1   % 1 .    Sedangkan  untuk % 1 , didapat dari penjumlahan antara pada , dengan pada , - yang masing  besarnya 0 dan % 2 yang  kemudian dijumlah lagi dengan 1 , sehingga akan dihasilkan 0   % 2  1    % 1 .
Dengan  menggunakan  contoh  sebarang graf  lainnya,  misalkan  graf  sikel + H dikalikan kartesius dengan graf bipartisi 5 , .
X Graf + 4 = 2 = 1 Graf 5 1,2 = 2 = 1 Graf + 4 x 5 1,2 = 2 + 2 = 4 = 1 + 1 + 1 = 3 X
Gambar 10. Perkalian Kartesius antara Graf + H dengan Graf 5 ,
Dari  hasil  di  atas  diperoleh  bahwa ฀ pada graf + H 5 , adalah 4, yang didapat dari  penjumlahan pada  graf + H yang bernilai 2 dengan pada graf 5 , yang juga bernilai  2.  Sedangkan pada  graf + H 5 , adalah 3, yang didapat  dari penjumlahan pada graf + H yang bernilai 1 dengan pada graf 5 , yang  juga  bernilai  1  dan  ditambah dengan 1 . Hasil  ini  bukanlah  suatu  kebetulan  yang muncul dari contoh-contoh yang telah ditampilkan.  Akan  tetapi  ini  adalah  suatu  pola yang  terdapat  pada  setiap  graf  dari  hasil perkalian kartesius dua graf. Setiap sebarang graf jika  dikalikan  dengan  sebarang  graf , maka hasilnya  akan  isomorfik  dengan  graf yang titik-titiknya  adalah  graf . Begitu  juga sebaliknya  hasilnya  akan  isomorfik  dengan  graf yang titik-titiknya adalah graf . Dari  contoh  di  atas,  misalnya  graf adalah  graf  sikel + H akan  dikalikan  kartesius dengan yaitu  graf  bipartisi 5 , .  Maka menghasilkan graf dengan graf bipartisi 5 , akan menggantikan titik-titik pada graf  sikel + H .
Graf 2 Graf 2 Graf 2 Graf 2 Gambar 11. Graf + H 5
,
Dengan  memperhatikan  hasil-hasil  di atas diperoleh sebagai berikut:
Teorema 8 Graf adalah  graf  hasil  perkalian  kartesius sebarang  graf  terhubung dan  sebarang  graf
terhubung .  Bilangan rainbow  connection dari graf adalah: "# "# $ $ sedangkan  bilangan rainbow  vertex-connection dari graf adalah: "# "# % 1  $ $ 1 Bukti: Graf graf hasil  kali  kartesius  adalah  graf  yang dinotasikan dan  mempunyai  titik ,  dan  dua  titik , dan
, dari  graf terhubung  langsung  jika  dan hanya jika dan atau dan . i Akan  dibuktikan  jika maka "# "# dan $ Diketahui jika maka "#    "# "# , karena "# maka
"# "#
. Selanjutnya  misalkan n ,  artinya dengan  bilangan  warna  sisi  minimum sebanyak n akan  membuat  graf menjadi graf  pelangi  sisi  yang  terhubung,  dan b ,  artinya  dengan  bilangan  warna sisi minimum sebanyak b akan membuat graf menjadi graf pelangi sisi yang terhubung.
Kemudian V , X , dengan ", Z 1,2, … , , serta
 ,  , dengan , . 1,2, … , # maka V ,  , M X ,  N  . Jika lintasan V % X membentuk lintasan pelangi dengan warna  sisi  maka $ n ,  dan  jika  % て  membentuk lintasan pelangi dengan _ warna  sisi  maka _ $ b .  Akan dibuktikan lintasan
V ,  % X ,  membentuk  lintasan  pelangi  dengan  warna sisi $ n  b . Ada 4 kemungkinan, yaitu:
1) Lintasan V ,  % X ,  dengan "   Z   Y . . Himpunan  dari  titik-titik V ,  , X ,  dengan "   Z   Y . akan membentuk graf  yang  isomorfik  dengan  graf .  Dua titik  tersebut  bisa  terhubung  langsung dan  juga  bisa  tidak  terhubung  langsung akan tetapi keduanya pasti  dihubungkan oleh  lintasan.  Karena  setiap  %  membentuk  lintasan  pelangi  dengan _ warna  sisi  di  mana _ $ b .  Maka  Lintasan V ,  % V ,  juga  akan  membentuk lintasan  pelangi  dengan _ warna  sisi  di mana _ $ b . 2) Lintasan V ,  % X ,  dengan " Y Z dan . Himpunan  dari  titik-titik V ,  , X ,  dengan " Y Z dan . akan  membentuk
graf  yang  isomorfik  dengan  graf .  Dua titik  tersebut  bisa  terhubung  langsung dan  juga  bisa  tidak  terhubung  langsung akan  tetapi  keduanya  pasti  dihubungkan oleh  lintasan.  Karena  setiap V % X membentuk  lintasan  pelangi  dengan warna sisi di mana $ n . Maka Lintasan V ,  % V ,  juga  akan  membentuk lintasan  pelangi  dengan warna  sisi  di mana $ n . 3) Lintasan
V ,  % X ,  dengan " Z dan . Jika terdapat dua titik V ,  dan X ,  dengan "   Z dan . ,  maka  kedua  titik tersebut sama, sehingga panjang lintasan sama dengan 0.
4) Lintasan V ,  % X ,  dengan " Y Z dan Y . Jika terdapat dua titik V ,  dan X ,  dengan " Y Z dan Y . ,  maka  kedua  titik tersebut tidak mungkin terhubung langsung.
Sehingga kemungkinan lintasan  dengan  panjang  sisi  terbesar adalah  antara  kedua  titik  ini.  Lintasan antara  kedua  titik V ,  dan X , 
akan  membentuk  lintasan V ,  % M X ,  N % M X ,  N, sehingga  terdapat  dua langkah.  Pertama  lintasan V ,  % X ,  ,  lintasan  ini  akan  membentuk lintasan  pelangi  dengan warna  sisi  di mana $ n . Kemudian ditambah dengan lintasan M X ,  N % M X ,  N, yang membentuk  lintasan  pelangi  dengan _ warna  sisi  di  mana _ $ b. Sehingga Lintasan
V ,  % X ,  akan membentuk  lintasan  pelangi  dengan _ warna sisi di mana $ n dan _ $ b .
Jadi  terbukti
_ $ n  b
.
(ii) Akan  dibuktikan  jika maka "# "# % 1 dan $
1
Diketahui jika
maka
"#    "# "# ,  karena "#  % 1 maka "# "# % 1 .
Selanjutnya "# % 1 dan
"#
% 1,
ini berakibat
"# $ 1 dan "# $
1.
Karena
"#
"# % 1
maka $ 1 1 % 1
sehingga diperoleh:
$ 1 .
Jadi terbukti, jika . maka : "# "# % 1  $  $
1 .

## PENUTUP
Berdasarkan  hasil  pembahasan,  maka  dapat diambil kesimpulan sebagai berikut :
1. Penjumlahan  dua  graf dan yang dinotasikan ,  diperoleh  bilangan rainbow connection dari graf adalah:
1, dan graf komplit 2, atau bukan graf komplit sedangkan bilangan rainbow vertex- connection dari graf adalah: 0, dan graf komplit 1, atau bukan graf komplit
2. Graf graf hasil  kali  kartesius  adalah  graf
yang  dinotasikan ,    diperoleh
bilangan rainbow  connection dari  graf adalah:
"# "# $ $ sedangkan bilangan rainbow vertex- connection dari graf adalah: "# "# % 1  $ $ 1

## DAFTAR PUSTAKA
[1] Abdullah  bin  Muhammad.  2005. Tafsir Ibnu    Katsir  Jilid  8. Bogor:  Pustaka  Imam As-Syafi’i
[2] Abdussakir.  2007. Ketika  Kiai  Mengajar Matematika . Malang: UIN Malang Press
[3] Al-Hifnawi,  M.  I.  2009. Tafsir  Al-Qurthubi . Jakarta: Pustaka Azam.
[4] Al-Maraghi,  A.  M.  1989. Tafsir  Al-Maraghi . Semarang: CV. Toha Putra.
[5] Al-Qarni , ‘A. 2008. Tafsir Muyassar , jilid 3. Jakarta: Qitshi Press.
[6] Alisah, E & Dharmawan, E. P. Filsafat Dunia Matematika .  Jakarta:  Prestasi  Pustaka Publisher.
[7] Bondy,  J.  A  &  Murty,  U.S.R.  1976. Graph Theory With Applications . London: MacMillan Press
[8] Chandran,  L.  Sunil. Rainbow  Coloring  of Graph. (Online: www.tcs.tifr.res.in/.../ nitk.../combinatore.pdf diakses pada tanggal 31 april 2012)
[9] Chartrand,  G.  &  Lesniak,  L.  1986. Graphs and  Digraphs  Second  Edition .  California:  a Division of Wadsworth, Inc.
[10] Harary,  F.  1969. Graph  Theory. Amerika: Addison-Wesley Publishing Company, inc.
[11] J.  A.  Gallian.  2007. A  dynamic  Survey  of Graph Labeling . Electronic journal combinatorics. Dynamic Survey D#56
[12] Krivelevich,    M.  &  Yuster,    R.  2010. The Rainbow connection of a graph is (at most) reciprocal to its minimum degree , School of Mathematics, Tel Aviv University. [13] Purwanto. 1998. Matematika Diskrit . Malang: IKIP Malang.
[14] Quthb,  S.  2004. Tafsir  Fi  Zhilalil  Qur’an . Jakarta: Gema Insani
[15] Y.  Caro,  A.  Lev,  Y.  Roditty,  Z.  Tuza,  and  R. Yuster,  On  rainbow  connection, Electronic
Journal  of  Combinatorics 15  (2008),  #R57