Generalisasi Pertidaksamaan Euler untuk Membuktikan Planaritas Graf K_5 dan K_(3,3)

Abstract

Kajian literatur tentang teori graf, khususnya planaritas suatu graf, yaitu menentukan apakah suatu graf itu termasuk graf planar atau bukan sudah banyak dibahas. Pada artikel ini pembahasan sedikit berbeda yaitu melakukan generalisasi atau perumuman teorema planaritas untuk  dan teorema planaritas untuk Eksistensi perumuman ini penting karena dapat membuktikan planaritas  dan sekaligus  serta planaritas beberapa graf yang terkait. Pembuktian ketidakplanaran graf lengkap  dan  memberikan manfaat besar terhadap pengembangan teori planaritas graf dan memantapkan jaminan kebenaran pada terapannya. Urgensi pembuktiannya memiliki peran yang besar dalam menentukan planaritas graf-graf yang terkait, baik isomorfik atau subdivisi. Salah satu produk yang dihasilkan adalah teorema Kuratovski yang memberikan syarat perlu dan cukup suatu graf merupakan graf planar. Proses generalisasi dilakukan melalui kajian terhadap sifat-sifat khusus pada  dan juga sifat-sifat khusus yang dimiliki . Sifat-sifat khusus tersebut diperumum sehingga diperoleh suatu sifat yang berlaku baik untuk  maupun . Berdasarkan hasil generalisasi dari sifat tersebut, kemudian dikombinasikan dengan teorema pertidaksamaan Euler menghasilkan suatu teorema yaitu jika  suatu graf planar terhubung,  dan panjang sikel terpendeknya adalah , dengan maka berlaku  £  Manfaat dari generalisasi ini dapat juga digunakan pada pembuktian  dan  secara langsung dan beberapa graf terkait secara mudah.

Generalization of Euler's Inequality to Prove Planarity of Graphs K_5 and K_(3,3) 

Abstract

The study of literature on graph theory, especially the planarity of a graph, which is to determine whether a graph is a planar graph or a non-planar graph, has been widely discussed. This article's discussion is slightly different, namely generalizing the planarity theorem for  and the planarity theorem for  This generalization is important because it can prove the planarity of  and  and the planarity of several related graphs. Proving the unplanarity of complete graphs  and  provide significant benefits to developing graph planarity theory and strengthens the guarantee of truth in its application. The urgency of the proof has a significant role in determining the planarity of the related graphs, either isomorphic or subdivision. One of the products of its role is the birth of Kuratovski's theorem, which provides the necessary and sufficient conditions for a planar graph. The generalization process is carried out by studying the special properties of  and . These unique properties are generalized to obtain a valid property for  and . Based on the results of the generalization of these properties, then combined with the Euler inequality theorem and the resulting theorem is if  is a planar graph, connected,  and the length of the shortest cycle is k, with  then applies  £  (n-2). The benefits of this generalization can be used to prove  and  directly and some related graphs quickly. 

Penulisan artikel ini bertujuan untuk melakukan generalisasi atau perumuman teorema planaritas untuk K_5 dan teorema planaritas untuk K_3,3. Eksistensi perumuman teorema ini penting karena dapat membuktikan planaritas K_5 dan sekaligus K_3,3 serta planaritas beberapa graf yang terkait. Artikel ini merupakan hasil kajian literatur tentang teori graf, khususnya planaritas suatu graf, yaitu menentukan apakah suatu graf itu termasuk graf planar atau graf tidak planar. Pembuktian ketidakplanaran graf lengkap K_5 dan K_3,3 memberikan manfaat besar terhadap pengembangan teori planaritas graf dan memantapkan jaminan kebenaran pada terapannya. Urgensi pembuktiannya memiliki peran yang besar dalam menentukan planaritas graf-graf yang terkait, baik isomorfik atau subdivisi. Salahsatu produk perannya adalah lahirnya teorema Kuratovski yang memberikan syarat perlu dan cukup suatu graf planar. Teorema Kurotavski menjelaskan bahwa suatu graf G adalah planar jika dan hanya jika G tidak memuat subgraph yang isomorfik dengan K5 atau K3,3 atau sebarang graf subdivisi dari K5 atau K3,3. Proses generalisasi teorema dilakukan melalui kajian terhadap sifat-sifat khusus pada K_5 dan sifat-sifat khusus yang dimiliki K_3,3. Sifat-sifat khusus tersebut diperumum sehingga diperoleh suatu sifat yang berlaku baik untuk K_5 dan K_3,3. Berdasarkan hasil generalisasi sifat tersebut, kemudian dikombinasikan pada teorema pertidaksamaan Euler dan dihasilkan teorema yaitu jika G suatu graf planar, terhubung, |V(G)|=n, |E(G)|=m dan panjang sikel terpendeknya adalah k, dengan k3 maka berlaku . Teorema generalisasi ini mampu membuktikan K_5 dan K_3,3 secara langsung dan beberapa graf terkait secara mudah.