Sebuah jalan (walk) u – v di graf G adalah barisan berhingga (tak kosong). W : u = v0, e1, v1, e2, v2, ...., en – vn = v yang berselang seling antara titik dan sisi, yang dimulai dari titik dan diakhiri dengan titik sedemikian hingga untuk 0≤ i ≤ n. Dengan ei = vi-1vi adalah sisi di G.
v0 disebut titik awal, vn disebut titik akhir, v1, v2, ..., vn-1 disebut titik interval, dan n menyatakan panjang dari W (Chartrand dan Lesniak, 1986:26)

Derajat suatu titik v pada sebuah graf G, ditulis dengan deg(v), adalah jumlah sisi yang incident pada v. Dengan kata lain, jumlah sisi yang memuat v sebagai titik ujung. Titik v dikatakan genap atau ganjil tergantung dari jumlah deg(v) genap atau ganjil (Chartrand dan Lesniak, 1986: 8)

Graf G adalah pasangan himpunan (V, E) dengan V adalah himpunan tidak kosong dan berhingga dari obyek-obyek yang disebut sebagai titik dan E adalah himpunan (mungkin kosong) pasangan tak berurutan dari titik-titik berbeda di G yang disebut sebagai sisi. Himpunan titik di G dinotasikan dengan V(G) dan himpunan sisi dinotasikan dengan E(G). Sedangkan banyaknya unsur di V disebut order dari G dan dilambangkan dengan p(G) dan banyaknya unsur di E disebut ukuran dari G dan dilambangkan dengan q(G). Jika graf yang dibicarakan hanya graf G, maka order dan ukuran dari G tersebut cukup ditulis dengan p dan q (Chartrand dan Lesniak, 1986:4).
Dari uraian di atas, maka suatu graf tidak boleh mempunyai sisi rangkap dan loop. Sisi rangkap dari suatu graf adalah jika dua titik yang dihubungkan oleh lebih dari satu sisi. Sedangkan yang disebut dengan loop adalah suatu sisi yang menghubungkan suatu titik dengan dirinya sendiri (Suryanto dalam Fitria, 2007:6). Graf yang mempunyai sisi rangkap dan loop sebut multigraf.

Dewasa ini semakin banyak muncul penggunaan model matematika maupun penalaran matematika sebagai alat bantu dalam menyelesaikan permasalahan yang dihadapi dalam berbagai disiplin ilmu. Teori graf merupakan salah satu cabang matematika yang penting dan banyak manfaatnya karena teori-teorinya dapat diterapkan untuk memecahkan masalah dalam kehidupan sehari-hari. Dengan mengkaji dan menganalisa model atau rumusan teori graf dapat diperlihatkan peranan dan kegunaannya dalam memecahkan permasalahan. Permasalahan yang dirumuskan dengan teori graf dibuat sederhana, yaitu diambil aspek-aspek yang diperlukan dan dibuang aspek-aspek lainnya
Terkait dengan pernyataan di atas, pewarnaan titik pada graf merupakan salah satu dari materi pada teori graf yang berkembang dan mendapat perhatian saat ini. Dengan mengkaji dan menganalisis suatu pewarnaan titik pada graf tertentu, akan didapat suatu perumusan yang akan lebih memudahkan proses pengaplikasiannya ke dunia nyata.

Matematika merupakan salah satu cabang ilmu yang mendasari berbagai macam ilmu yang lain dan selalu menghadapi berbagai macam fenomena yang semakin kompleks. Hal ini disebabkan oleh kemajuan ilmu pengetahuan dan teknologi, serta matematika merupakan bahasa proses, teori dan aplikasi ilmu yang memberikan suatu bentuk dan kemanfaatan. Perhitungan matematika menjadi dasar bagi desain ilmu teknik, fisika, kimia maupun disiplin ilmu yang lainnya. Para ahli dari berbagai disiplin ilmu, menggunakan matematika untuk berbagai keperluan yang berkaitan dengan keilmuan mereka. Misalnya para ahli fisika menggunakan matematika untuk mengukur kuat arus listrik, merancang pesawat ruang angkasa, menganalisis gerak, mengukur kecepatan,

KODE B
1. Tentukan nilai n, jika (n+1)! / (n-2)! = 210
2. Jika diperlukan 4 orang laki-laki dan 7 orang perempuan untuk membentuk suatu barisan sedemikian hingga, tentukan banyak kemungkinan susunan barisan itu jika laki-laki harus di pinggir.
3. Ada 5 buku matematika, 7 buku kimia dan 6 buku fisika, akan di tata di sebuah rak buku. Dengan berapa cara buku itu di tata di rak, jika buku yang sejenis harus bersama.
4. Pak indra membeli 5 sepeda dan 7 mobil, jika tersedia 9 sepeda dan 8 mobil, berapa cara pak indra dapat memilih sepeda dan mobil,
5. Dari 30 kartu yang diberi nomor 1.2.3...30, untuk setiap kartu, diambil sebuah kartu secara acak, tentukan peluang terambilnya kartu kelipatan 6 atau 3.
6. Satu kotak berisi 11 bola biru dan 14 bola merah, diambil 2 bola secara berurutan tanpa pengembalian bola pertama, tentukan peluang terambilnya bola merah pada pengambilan pertama dan bola biru di pengambilan kedua.
7. Dari sebuah kotak berisi 7 buah semangka dan 8 buah melon di ambil 6 buah sekaligus, tentukan berapa peluang paling sedikit terambil 1 buah melon.

KODE A
1.Tentukan nilai n, jika (n-1)! / (n-3)!=132
2. Jika diperlukan 5 orang laki-laki dan 6 orang perempuan untuk membentuk suatu barisan sedemikian hingga, tentukan banyak kemungkinan susunan barisan itu jika wanita harus di pinggir.
3. Ada 4 siswa kelas VII, 5 siswa kelas VIII dan 6 siswa kelas IX, mereka duduk mengelilingi meja bundar. Dengan berapa cara mereka dapat duduk mengelilingi meja bundar, jika yang kelasnya sama harus duduk bersama.
4. Pak doni membeli 4 ekor kambing dan 5 ekor sapi, jika tersedia 10 ekor kambing dan 8 ekor sapi, berapa cara pak doni dapat memilih kambing dan sapi.
5. Dari 25 kartu yang diberi nomor 1.2.3...25, untuk setiap kartu, diambil sebuah kartu secara acak, tentukan peluang terambilnya kartu dengan nomor kelipatan 5 atau 2.
6. Satu kotak berisi 10 bola putih dan 15 bola hijau, diambil 2 bola secara berurutan tanpa pengembalian bola pertama, tentukan peluang terambilnya bola hijau pada pengambilan pertama dan bola putih di pengambilan kedua.
7. Dari sebuah kantong berisi 6 kelereng kuning dan 7 kelereng biru di ambil 5 kelereng sekaligus, tentukan berapa peluang paling sedikit terambil 1 kelereng kuning.