## BILANGAN RAINBOW CONNECTION BERDASARKAN DERAJAT MINIMUM PADA GRAF

## Widya Anggraini, M.Mahfuzh Shiddiq, Pardi Affandi
Program Studi Matematika Fakultas MIPA Universitas Lambung Mangkurat Jl. Jend. A. Yani km. 36 Banjarbaru 70714, Kalsel
Email: pedrosista.liverpudlian@gmail.com

## ABSTRACT
Graph 𝐺𝐺 =  ( 𝑉𝑉 , 𝐸𝐸 ) consists of 2 sets, that are the not empty set 𝑉𝑉 and set 𝐸𝐸 which are the elements of 𝑉𝑉 are called  vertex  and  the  elements of 𝐸𝐸 are called  edge. The number of edges which are connected with vertex 𝑉𝑉 is called the degree and minimum of the number of edges which connected with vertex 𝑉𝑉 on graph 𝐺𝐺 is called minimum degree ( 𝛿𝛿 ( 𝐺𝐺 )) . One of the topics  studied in the coloring of  the  graph is the  rainbow  connection.  Coloring    edge  in 𝐺𝐺 is called  rainbow connected  if  every  two  distinct vertices are connected  by  a rainbow path.  Rainbow  connection numbers  of a 𝐺𝐺 connected graph  which is written with 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) is  the minimum  of  the number of colors  needed to make 𝐺𝐺 to rainbow connected. The purpose of this study is to prove the rainbow connection numbers in the graph is based on minimum degree of graph. In this paper, we search rainbow connected numbers for 2-connected graphs and 2-connected graph that does not contains a bridge. Finally, the result of those two graph is used to searching for rainbow connected numbers of graphs with a minimum degree of 3 The result of this research is for a connected graph G , if it has δ ≥ 3 then it has rainbow connection numbers more than 5n/6 . Keywords : graph, degree, rainbow connection numbers.

## ABSTRAK
Graf 𝐺𝐺 = ( 𝑉𝑉 , 𝐸𝐸 ) terdiri dari 2 himpunan yaitu himpunan tak kosong 𝑉𝑉 dan himpunan 𝐸𝐸 yang mana elemen 𝑉𝑉 disebut titik dan elemen 𝐸𝐸 disebut sisi. Banyaknya sisi  yang berhubungan dengan titik 𝑉𝑉 disebut derajat dan minimum dari banyaknya sisi yang berhubungan dengan titik 𝑉𝑉 pada graf 𝐺𝐺 disebut derajat minimum ( 𝛿𝛿 ( 𝐺𝐺 )) . Salah satu topik yang dipelajari dalam pewarnaan pada graf adalah rainbow connection . Pewarnaan sisi di 𝐺𝐺 dikatakan rainbow connected jika setiap dua titik yang berbeda dihubungkan oleh lintasan rainbow . Bilangan rainbow connection dari graf terhubung 𝐺𝐺 ditulis 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) yaitu minimum dari banyaknya warna yang diperlukan untuk membuat 𝐺𝐺 bersifat rainbow connected. Tujuan dari penelitian ini adalah untuk menentukan bilangan rainbow connection dalam graf berdasarkan derajat minimumnya. Penelitian dilakukan dengan cara mencari bilangan rainbow connected untuk graf 2-terhubung. Langkah berikutnya dicari juga untuk kasus graf  2-terhubung yang tidak memuat jembatan. Tahap terakhir dari dua dua graf tersebut dilakukan pencarian bilangan rainbow connected untuk graf dengan derajat minimum 3. Hasil dari penelitian ini adalah untuk graf terhubung 𝐺𝐺 , jika memiliki 𝛿𝛿 ≥ 3 maka memiliki bilangan rainbow connection lebih dari 5 𝑛𝑛 /6 . Kata Kunci :graf, derajat, bilangan rainbow connection .

## 1. PENDAHULUAN
Pencarian  bilangan  rainbow  connected muncul pertama kali dikenalkan oleh Chartand [2]. Sebuah pewarnaan sisi pada suatu graf dengan syarat pada suatu lintasan tidak ada ada yang berwarna sama. Penelitian di kasus ini dapat dilihat diberbagai sudut pandang, diantaranya dilihat dari graf komplemennya (Li dkk. [8]), dilihat dari jari-jari graf (Basavaraju dkk. [10]).
Pada penelitian akan dicari  bilangan rainbow connected dilihat dari sudut pandang derajat minimum suatu graf. Tulisan ini merupakan kajian ulang dari penelitian Caro [9]. Graf pada tulisan ini adalah graf berhingga, tak berarah dan sederhana.

## 2. TINJAUAN PUSTAKA
Berikut adalah beberapa definisi dan hasil-hasil yang dijadikan acuan pada pembahasan yang berkaitan dengan graf rainbow connected.

## Definisi 2.1 [4]
Misalkan 𝐺𝐺 adalah suatu graf terhubung tak trivial didefinisikan suatu pewarnaan sisi c : E(G) → {1, 2, …, n} n ∈ ℕ dimana sisi yang bertetangga boleh berwarna sama. Misalkan P adalah lintasan 𝑢𝑢 − 𝑣𝑣 di graf 𝐺𝐺 , 𝑃𝑃 disebut  lintasan rainbow  jika dan hanya jika untuk sebarang dua sisi di 𝑃𝑃 tidak memiliki warna yang sama.
Definisi 2.2 [4] Bilangan rainbow connection  dari graf terhubung 𝐺𝐺 , ditulis 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) didefinisikan sebagai minimum dari banyaknya warna  yang diperlukan untuk membuat 𝐺𝐺 bersifat rainbow connected.
Lemma 2.3 [4] Jika 𝐺𝐺 merupakan graf terhubung tak trivial dengan banyaknya sisi 𝑚𝑚 , maka 𝑑𝑑𝑑𝑑𝑑𝑑𝑚𝑚 ( 𝐺𝐺 ) ≤ 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) ≤ 𝑠𝑠𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) ≤ 𝑚𝑚 dimana 𝑑𝑑𝑑𝑑𝑑𝑑𝑚𝑚 ( 𝐺𝐺 ) merupakan diameter pada 𝐺𝐺 .
Teorema  2.4 [4] Misalkan G merupakan graf terhubung tak trivial yang berukuran m.
a) 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) = 𝑠𝑠𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) = 1 jika dan hanya jika graf 𝐺𝐺 merupakan graf lengkap, b) 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) = 2 jika dan hanya jika 𝑠𝑠𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) = 2 .
Lemma 2.5 [9] Jika 𝐺𝐺 adalah graf terhubung dan H 1 ,…,H k adalah partisi dari himpunan titik pada 𝐺𝐺 ke dalam subgraf terhubung, maka 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) ≤ 𝑘𝑘 − 1 + ∑ 𝑟𝑟𝑟𝑟 ( 𝐻𝐻 𝑖𝑖 ) 𝑘𝑘 𝑖𝑖=1
Teorema  2.6 [4]
Untuk setiap bilangan bulat positif  n ≥ 4, maka rc(C n ) = src(C n ) = � 𝑛𝑛 2 � .

## 3. METODOLOGI
Penelitian dilakukan dengan menentukan terlebih dahulu bilangan rainbow connected dari graf 2-terhubung. Selanjutnya, peneltian  juga mencari bilangan rainbow connected untuk graf 2-terhubung  yang tidak memuat jembatan. Hasil dari bilangan rainbow connected dua graf tersebut dijadikan landasan pada pencarian bilangan rainbow connected graf dengan derajat minimum 3.
4. HASIL DAN PEMBAHASAN
4.1 Bilangan Rainbow Connection pada graf 2-terhubung
Proposisi 4.1.1
Jika G adalah sebuah graf 2-terhubung dengan n titik maka 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) ≤ 2𝑛𝑛 3
Bukti : Karena 𝐺𝐺 adalah graf 2-terhubung sehingga jika G adalah sebuah graf C 5 ,  yang dalam hal ini merupakan graf 2-terhubung dengan 5 titik, maka  berdasarkan definsi 2.2 diketahui 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) = 3 sehingga  Proposisi  4.1.1  berlaku dikasus ini. Misalkan H adalah sebuah subgraf maksimal terhubung dari G yang memiliki sifat
𝑟𝑟𝑟𝑟 ( 𝐻𝐻 ) ≤ 2ℎ 3 − 2
3
dengan h sebagai banyaknya titik di H . Akan ditunjukkan bahwa H ada.
Kasus 1. Jika G mempunyai subgraf berupa segitiga ( C 3 ) maka H adalah subgraf berbentuk segitiga tersebut. Sehingga diperoleh
𝑟𝑟𝑟𝑟 ( 𝐻𝐻 ) = 1 ≤ 2(3) 3 − 2 3 𝑟𝑟𝑟𝑟 ( 𝐻𝐻 ) = 1 ≤ 2 − 2 3 = 4 3
Kasus 2.
Jika G mempunyai sebarang subgraf berupa C k , dengan 𝑘𝑘 ≥ 4 dan 𝑘𝑘 ≠ 5 maka H adalah subgraf C k tersebut sehingga berdasarkan teorema 2.6 diperoleh
𝑟𝑟𝑟𝑟 ( 𝐻𝐻 ) = � 𝑘𝑘 2 � ≤ 2 𝑘𝑘 3 − 2 3 = 2( 𝑘𝑘 − 1) 3
Kasus 3.
Jika setiap subgraf G berupa C 5 maka H adalah  subgraf C 5 tersebut yang ditambah satu sisi.
Pada pembahasan diawal Proposisi  4.1.1  diketahui jika C 5 memiliki 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) = 3 dan jika C 5 ditambah dengan satu sisi diperoleh 𝑟𝑟𝑟𝑟 ( 𝐻𝐻 ) tetap yaitu 𝑟𝑟𝑟𝑟 ( 𝐻𝐻 ) = 3, sehingga diperoleh 𝑟𝑟𝑟𝑟 ( 𝐻𝐻 ) = 3 . 𝑟𝑟𝑟𝑟 ( 𝐻𝐻 ) ≤ 2 𝑘𝑘 3 − 2 3 𝑟𝑟𝑟𝑟 ( 𝐻𝐻 ) = 3 ≤ 4 − 2 3
Akan ditunjukkan bahwa ℎ ≥ 𝑛𝑛 − 2 . Diasumsikan bahwa ada tiga titik di luar H , misalkan 𝑥𝑥 1 , 𝑥𝑥 2 , 𝑥𝑥 3 dimana setiap titik mempunyai  dua tetangga di H (dimana tetangga 𝑥𝑥 𝑖𝑖 tidak harus berbeda dengan tetangga 𝑥𝑥 𝑗𝑗 ). Selanjutnya di titik 𝑥𝑥 1 , 𝑥𝑥 2 , 𝑥𝑥 3 ditambahkan  ke H dan membentuk sebuah subgraf 𝐻𝐻′ dengan h + 3 titik.  Misalkan e i dan f i adalah dua sisi yang menghubungkan x i dengan H dan hanya  digunakan 2 warna baru untuk mewarnai 6 sisi baru yaitu sisi-sisi 𝑒𝑒 1 , 𝑒𝑒 2 , 𝑒𝑒 3 memiliki warna yang sama dan sisi-sisi 𝑓𝑓 1 , 𝑓𝑓 2 , 𝑓𝑓 3 memiliki warna yang sama. Sehingga diperoleh
ISSN: 1978-4422 Vol.12 No.2 (Desember 2018) Hal. 52- 60
𝑟𝑟𝑟𝑟 ( 𝐻𝐻 ′ ) ≤ 𝑟𝑟𝑟𝑟 ( 𝐻𝐻 ) + 2 ≤ 2ℎ 3 − 2 3 + 2 = 2( ℎ + 3) 3 − 2
3 sehingga  berdasarkan  definisi  komponen graf, kontradiksi dengan pernyataan bahwa H merupakan subgraf maksimal. Hal ini menunjukkan bahwa jika terdapat tiga titik diluar H maka  setidaknya terdapat satu titik, misalkan x ,  memiliki  sifat bahwa untuk sebuah lintasan terpendek dari H ke 𝐻𝐻′ yang melalui x mempunyai panjang setidaknya 3 (lintasan harus merupakan graf 2-terhubung. Oleh karena itu, misalkan 𝑑𝑑 , 𝑥𝑥 𝑖𝑖 , … , 𝑏𝑏 dimana 𝑑𝑑 , 𝑏𝑏 ∈ 𝐻𝐻 membentuk sebuah lintasan dengan 𝑥𝑥 1 , … , 𝑥𝑥 𝑡𝑡 ∉ 𝐻𝐻 dan 𝑡𝑡 ≥ 2 . Hubungkan 𝑥𝑥 1 , … , 𝑥𝑥 𝑡𝑡 , ke H dan membentuk sebuah subgraf 𝐻𝐻′ dengan  h + t titik.  Jika t ganjil, maka  dapat diberikan warna pada  t + 1 sisi dari lintasan dengan 𝑡𝑡+1 2 warna  baru.  Setengah pertama dari lintasan berwarna berbeda, dan setengah kedua  lainnya diberikan warna dengan urutan yang sama dengan   setengah yang pertama. Ini membuktikan bahwa 𝐻𝐻′ adalah rainbow connected .  Jika t  genap, maka dapat diwarnai  t + 1 sisi dari lintasan dengan 𝑡𝑡 2 warna  sebagai berikut; Sisi tengah( 𝑋𝑋 𝑡𝑡 / 2 , 𝑋𝑋 𝑡𝑡 2 +1 )  memiliki beberapa warna yang sudah ada di H . Pada sisi 𝑡𝑡 2 pertama dari lintasan memiliki warna baru yang berbeda dan di sisi 𝑡𝑡 2 terakhir dari lintasan diwarnai berulang dengan warna dan urutan yang sama. Karena 𝐻𝐻′ adalah subgraf dari graf H yang dihubungkan dengan t titik di luar H dan lintasannya  diberikan 𝑡𝑡 2 warna di awal dan berulang sampai akhir lintasan, maka diperoleh
𝑟𝑟𝑟𝑟 ( 𝐻𝐻 ′ ) ≤ 𝑟𝑟𝑟𝑟 ( 𝐻𝐻 ) + � 𝑡𝑡 2 � ≤ 2ℎ 3 − 2 3 + � 𝑡𝑡 2 � ≤ 2( ℎ + 𝑡𝑡 ) 3 − 2 3 kontradiksi dengan pernyataan  bahwa 𝐻𝐻 subgraf maksimal. Jadi haruslah ℎ ≥ 𝑛𝑛 − 2 maka terbukti 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) ≤ 2 ( 𝑛𝑛−3 ) 3 − 2 3 + 2 = 2𝑛𝑛 3 .

## 4.2  Bilangan Rainbow connection pada graf 2-terhubung tanpa jembatan
Proposisi 4.2.1
Jika 𝐺𝐺 adalah sebuah graf 2-terhubung  tanpa jembatan dengan n titik maka 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) ≤ 4𝑛𝑛 5 − 1
Bukti : Pertama tinjau kasus dimana 𝐺𝐺 adalah graf 2-terhubung. Maka berdasarkan Proposisi 4.1.1 diketahui bahwa 𝐺𝐺 memiliki 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) ≤ � 2𝑛𝑛 3 � dan akan dicari nilai n dari graf 𝐺𝐺 yang memenuhi 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) ≤ � 2𝑛𝑛 3 � ≤ 4𝑛𝑛 5 − 1 � 2𝑛𝑛 3 � ≤ � 4𝑛𝑛 5 − 1 �
⌊ 15 ≤ 12 𝑛𝑛 − 10 𝑛𝑛 ⌋
⌊ 7,5 ⌋ ≤ 𝑛𝑛
7 ≤ 𝑛𝑛
Berdasarkan pembahasan di atas diketahui bahwa graf G yang  memiliki 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) ≤ [ 2𝑛𝑛 ] 3 ≤ 4𝑛𝑛 5 − 1 adalah graf G yang memiliki 𝑛𝑛 ≥ 7 . Graf 2-terhubung adalah graf cycle yang diketahui dari Lemma 2.5 memiliki 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) ≤ 𝑛𝑛 − 2 sehingga akan dicari nilai n yang memenuhi 𝑛𝑛 − 2 ≤ 4𝑛𝑛 5 − 1 𝑛𝑛 − 2 ≤ � 4 𝑛𝑛 5 − 1 � 5 𝑛𝑛 − 10 ≤ 4 𝑛𝑛 − 5
5 𝑛𝑛 − 4 𝑛𝑛 ≤ − 5 + 10 𝑛𝑛 ≤ 5
Berdasarkan pembahasan di atas diketahui bahwa graf G yang  memiliki 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) ≤ 𝑛𝑛 − 2 ≤ 4𝑛𝑛 5 − 1 adalah graf G yang memiliki 𝑛𝑛 ≤ 5 , yaitu 𝑛𝑛 = 3,4,5 . Graf dengan 𝑛𝑛 = 1 dan 𝑛𝑛 = 2 tidak termasuk karena bukan merupakan graf 2-terhubung. Sehingga berdasarkan pembahasan di atas maka kasus yang tersisa hanya jika 𝑛𝑛 = 6 dan akan ditunjukkan bahwa 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) ≤ 3 dalam kasus ini.
Kasus 1 Jika cycle terpanjang dari G memiliki panjang 6 maka 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) ≤ 3.
Diketahui 𝑛𝑛 = 6 sehingga diperoleh,
𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) ≤ � 4 𝑛𝑛 5 − 1 � 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) ≤ ⌊ 3,8 ⌋ 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) ≤ 3
Berdasarkan  pembahasan di atas maka terbukti jika graf G dengan 𝑛𝑛 = 6 memiliki 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) ≤ 3 .
Kasus 2 Jika cycle terpanjang memiliki panjang 5 maka G adalah graf C 5 dan titik berderajat 2 lain yang bertetangga adalah 2 titik yang tidak berdekatan di cycle . Diketahui bahwa jika  graf cycle dengan panjang 5 memiliki 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) = 3 sehingga walaupun ditambah dengan satu titik tetap memiliki 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) = 3 .
Kasus 3 Jika cycle terpanjang memiliki panjang 4 maka G adalah K 2,4 yang  memiliki 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) = 2 .
Bukti: Diketahui bahwa graf K 2,4 adalah graf cycle yang mempunyai panjang 4, yaitu: (V 3 ,V 1 ,V 4 ), (V 1 ,V 4 ,V 2 ), (V 1 ,V 5 ,V 2 ) dan (V 1 ,V 6 ,V 2 ) serta memiliki 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) = 2 . Ini juga membuktikan bahwa graf dengan n = 6 memiliki panjang paling sedikit 4.
Setelah membuktikan proposisi graf 2-terhubung akan dibuktikan graf terhubung tanpa jembatan pada banyaknya komponen dari graf 2-terhubung. Misalkan X adalah kumpulan titik dari komponen graf 2-terhubung G sehingga X hanya terdiri dari satu titik potong, misalkan x (dianggap bahwa komponen graf     2-terhubung selalu ada). Misalkan subgraf H dari G terbentuk dari 𝑉𝑉 ( 𝐺𝐺 )\ 𝑋𝑋 ) ∪ { 𝑥𝑥 } .  Sehingga
diketahui bahwa subgraf H memiliki 𝑛𝑛 − | 𝑋𝑋 | + 1 titik dan terhubung, tanpa jembatan dan memiliki paling tidak satu komponen 2-terhubung.  Berdasarkan hipotesis maka diperoleh
𝑟𝑟𝑟𝑟 ( 𝐻𝐻 ) ≤ 4( 𝑛𝑛 − | 𝑋𝑋 | + 1) 5 − 1
Karena graf G adalah graf yang terbentuk dari subgraf H dan X maka
𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) ≤ 𝑟𝑟𝑟𝑟 ( 𝑋𝑋 ) + 𝑟𝑟𝑟𝑟 ( 𝐻𝐻 )
Sehingga diperoleh
𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) ≤ 4𝑛𝑛 5 − 2 + 4 5 < 4𝑛𝑛 5 − 1

## 4.3  Bilangan rainbow connection pada graf dengan
𝜹𝜹 ≥ 𝟑𝟑

## Teorema 4.3.1
Jika G adalah sebuah graf terhubung dengan n titik dan 𝛿𝛿 ≥ 3 maka 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) < 5 𝑛𝑛 /6
Bukti: Diberikan sebuah graf terhubung G = (V,E) dengan n titik dan memiliki derajat minimum paling sedikit 3. Dimisalkan 𝐵𝐵 ⊂ 𝐸𝐸 adalah himpunan dari  jembatan- jembatan di G . Jika 𝐵𝐵 = ∅ maka graf G adalah graf tanpa jembatan sehingga berdasarkan  Proposisi 4.2.1 diketahui  graf G memiliki 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) ≤ 4𝑛𝑛 5 − 1 . Selanjutnya jika 𝐵𝐵 ≠ ∅ .  Misalkan 𝒞𝒞 adalah himpunan dari komponen-komponen terhubung dari graf 𝐺𝐺 ′ = ( 𝑉𝑉 , 𝐸𝐸 \ 𝐵𝐵 ) . Karena G memiliki 𝛿𝛿 ≥ 3 maka 𝒞𝒞 juga memiliki 𝛿𝛿 ≥ 3 sehingga 𝒞𝒞 memiliki titik paling  sedikit 4. Misalkan 𝐺𝐺 ′ = ( 𝑉𝑉 , 𝐸𝐸 \ 𝐵𝐵 ) dan C adalah himpunan komponen terhubung dari 𝐺𝐺′ dan karena C pada 𝐺𝐺′ tidak mempunyai jembatan maka minimal anggota 𝐶𝐶 adalah 2 yaitu singleton dan subgraf terhubung tanpa jembatan. Misalkan 𝑆𝑆 ⊂ 𝒞𝒞 adalah singleton dan 𝒟𝒟 = 𝒞𝒞 \ 𝑆𝑆 .
Selanjutnya dibangun sebuah graf pohon berakar T yang simpul-simpulnya merupakan elemen dari 𝒞𝒞 yang menggunakan cara rekusif berikut :
1) Akar dari T diambil dari sebarang elemen di 𝒞𝒞 .
2) C adalah titik-titik yang ada di T
3) Anak-anak dari titik C  merupakan semua elemen dari 𝒞𝒞 yang dapat dicapai dari C melalui satu jembatan, selain orang tua C di T
4) Daun-daun dari T adalah titik-titik yang tidak mempunyai anak.
5) Urutkan anak-anak dari titik C  dari kiri ke kanan dan  untuk anak paling kiri dinotasikan sebagai ℓ ( C ) dan anak paling kanan dinotasikan 𝑟𝑟 ( C ) 6) L (C) merupakan daun paling kiri di subtree T yang berakar di C
Misalkan ℒ ⊂ 𝒞𝒞 adalah himpunan dari daun-daun di T . Diketahui bahwa ℒ adalah sebuah subset dari 𝒟𝒟 .  Karena masing-masing singleton di 𝑆𝑆 memiliki
ISSN: 1978-4422 Vol.12 No.2 (Desember 2018) Hal. 52- 60
𝛿𝛿 ≥ 3 maka menunjukkan bahwa 𝑠𝑠 ∈ 𝑆𝑆 memiliki paling sedikit dua anak di T , sehingga ℓ ( 𝑠𝑠 ) ≠ 𝑟𝑟 ( 𝑠𝑠 ) .  Akibatnya, karena setiap s memiliki anak paling sedikit 2 berarti T memiliki paling sedikit 2 daun untuk setiap s di T sehingga diketahui bahwa banyaknya s di T kurang dari banyaknya daun di T sehingga diperoleh | 𝑆𝑆 | ≤ | ℒ | .
Selanjutnya,  dengan alasan yang sama dimana setiap s memiliki anak paling sedikit 2 sehingga setiap s tidak mungkin memiliki anak yang sama, sehingga diketahui bahwa setiap pasang anak yaitu ℓ ( 𝑠𝑠 ) dan 𝑟𝑟 ( 𝑠𝑠 ) hanya memiliki satu orangtua sehingga 𝑠𝑠 1 ≠ 𝑠𝑠 2 . Karena 𝑠𝑠 1 ≠ 𝑠𝑠 2 maka 𝐿𝐿 ( 𝑟𝑟 ( 𝑠𝑠 1 )) ≠ 𝐿𝐿 ( 𝑟𝑟 ( 𝑠𝑠 2 )) sehingga berdasarkan definisi pemetaan diketahui bahwa pemetaan 𝒮𝒮 − ℒ adalah satu-satu sehingga 𝒮𝒮 → ℒ ( 𝑟𝑟 ( 𝑠𝑠 )) injektif.
Selanjutnya karena masing-masing singleton memiliki 𝛿𝛿 ≥ 3 maka elemen dari ℒ terdiri paling sedikit oleh empat titik. Jika 𝑋𝑋 ∈ ℒ maka X adalah sebuah subgraf terhubung tanpa jembatan dari G yang terhubung hanya dengan satu jembatan. Setiap titik dari X selain  yang  terhubung dengan jembatan memiliki semua tetangganya di X , dan karena G memiliki derajat minimum paling sedikit 3, maka | 𝑋𝑋 | ≥ 4 .
Selanjutnya 𝒮𝒮 yang memiliki 𝐿𝐿�𝑟𝑟 ( 𝑠𝑠 ) � yaitu daun yang terdapat pada anak yang terletak di paling kanan dipartisi menjadi 2 bagian, 𝒮𝒮 ′ dan 𝒮𝒮′′ dimana 𝒮𝒮′ adalah semua singleton s dari 𝐿𝐿 ( 𝑟𝑟 ( 𝑠𝑠 )) yang memiliki kardinalitas 4, dan 𝒮𝒮′′ adalah semua singleton s dari 𝐿𝐿 ( 𝑟𝑟 ( 𝑠𝑠 )) yang mempunyai kardinalitas paling sedikit 5.
Diketahui bahwa banyaknya singleton pada X diperoleh dari 𝑆𝑆′ yaitu partisi yang terdiri dari 4 S , dan 𝑆𝑆′′ yaitu partisi yang terdiri dari 5 S yaitu 4 S yang ditambah dengan S (orang tua dari 𝐿𝐿 ( 𝑟𝑟 ( 𝑠𝑠 )) ) serta S (akar dari subgraf X ). Karena S merupakan akar dari subgraf X maka S juga merupakan bagian dari 𝑆𝑆′ dan 𝑆𝑆′′ sehingga
| 𝑆𝑆 | + 4| 𝑆𝑆 ′ | + 5| 𝑆𝑆 " | = | 𝑆𝑆 ′ | + | 𝑆𝑆 ′′ | + 4| 𝑆𝑆 ′ | + 5| 𝑆𝑆 ′′ | = 5 | S' |+ 6 | S" | ≤ 𝑛𝑛 ……. (1)
Selanjutnya warnai E dengan warna yang membuat G menjadi rainbow connected . Setiap sisi dari masing-masing elemen 𝑋𝑋 𝜖𝜖 𝐷𝐷 diwarnai dengan 4 | 𝑋𝑋 | 5 − 1 . Kemudian warnai jembatan yang menghubungkan X dengan orangtuanya di T (kecuali jika X adalah akar dari T ) dengan menggunakan satu warna. Karena jembatan yang menghubungkan X dengan orangtuanya harus memiliki warna yang berbeda maka warnai X dan jembatan yang menghubungkan dengan orangtuanya di T menggunakan 4 | 𝑋𝑋 | 5 . Demikian juga, untuk setiap 𝑠𝑠 𝜖𝜖 𝑆𝑆 diberikan warna untuk jembatan yang menghubungkan s ke orangtuanya di T (kecuali jika X adalah orangtua dari T ) dengan satu dedikasi warna.
Diketahui | 𝑆𝑆 | adalah banyaknya titik pada S dan ∑ | 𝑋𝑋 | adalah banyaknya titik pada subgraf terhubung di G . Sehingga diperoleh | 𝑆𝑆 | − 1 + 4 5 ∑ 𝑋𝑋 = | 𝑆𝑆 | − 1 + 4 5 ( 𝑛𝑛 − | 𝑆𝑆 |) = | 𝑆𝑆 | − 1 + 4 5 𝑛𝑛 − 4 5 | 𝑆𝑆 | = 4 5 𝑛𝑛 + 1 5 | 𝑆𝑆 | − 1
Ingat bahwa setidaknya terdapat | 𝑆𝑆 ′ | elemen dari 𝒟𝒟 yang memiliki kardinalitas 4. Karena graf 2-terhubung dengan kardinalitas | 𝑋𝑋 | = 4 dapat menjadi rainbow connected hanya dengan menggunakan dua warna, maka tidak perlu menggunakan 4 | 𝑋𝑋 | 5 − 1 warna pada kasus ini, sebaliknya hanya menggunakan 4 | 𝑋𝑋 | 5 − 6 5 warna, yang menghemat tambahan 1 5 dalam perhitungan setidaknya | 𝑆𝑆 ′′ | kali. Sehingga
𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) ≤ 4 5 𝑛𝑛 + 1 5 | 𝑆𝑆 ′′ | − 1
Dengan persamaan (1), maka
| 𝑆𝑆 "| ≤ 𝑛𝑛 6 . Sehingga 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) < 5𝑛𝑛 6 terbukti.

## 5. KESIMPULAN
Berdasarkan pembahasan yang telah dilakukan diperoleh kesimpulan sebagai berikut:
1. Jika 𝐺𝐺 adalah graf 2-terhubung dengan n titik maka 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) ≤ 2 𝑛𝑛 /3
2. Jika 𝐺𝐺 adalah graf 2-terhubung  tanpa  jembatan  dengan  n  titik  maka 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) ≤ 4𝑛𝑛
5 − 1 .
3. Jika 𝐺𝐺 adalah    graf  terhubung dengan n titik dan memiliki 𝛿𝛿 ≥ 3 maka 𝑟𝑟𝑟𝑟 ( 𝐺𝐺 ) < 5 𝑛𝑛 /6

## 6.  DAFTAR PUSTAKA
[1]   B. Bolloba´s,.1978. Extremal Graph Theory , Academic Press, London.
[2]  Chartrand,G., dkk. 2008. Rainbow Connection in graph . Mathematica Bohemica .133: 85-98.
[3]   Diestel, R. 2005. Graph Theory . Springer-Verlag Heidelberg. New York
[4]   Gross, J.L., J. Yellen, & P. Zhang. 2014. Handbook Of Graph Theory . Taylor & Francis Group, LLC.
[5]   J.A.Bondy dan U.S.R.Murty. 2008. Graph Theory,GTM244. Springer. New York.
[6]  Munir.R. 2005. Metode Diskrit. Edisi ke-3 . Informatika, Bandung.
[7]  Skiena,S.1990. Implementing Discrete Mathematics:Combinatorics and Graph Theory with Mathematica. Cambridge University Press.
[8]  X.Li & Y. Sun. 2012. Rainbow Connections of Graphs . Springer Briefs In Mathematics, New York.
[9]  Y.Caro, A. Lev, Y. Roditty, Z. Tuza, R. Yuster. 2008. On rainbow connection, Electronic J. Combin, 15, R57.
[10] Basavaraju, M., Chandran, L.S., Rajendraprasad, D. and Ramaswamy, A., 2010. Rainbow connection number and radius. arXiv preprint arXiv:1011.0620.