Graf Petersen

Dalam teori graf, salah satu disiplin ilmu matematika, graf Petersen merupakan salah satu graf istimewa yang terkenal karena menjadi bukti penyangkal beberapa konjektur dalam teori graf. Graf ini dinamai atas matematikawan Denmark, Julius Petersen, ketika dia mengkonstruksi graf ini sebagai sebuah contoh graf kubik tanpa jembatan yang tidak memiliki 3-pewarnaan-sisi.

Donald Knuth, dalam bukunya "The Art of Computer Programming" berpendapat bahwa struktur graf ini sangat istimewa. Banyak sekali sifat-sifat dalam teori graf yang sepintas terasa benar namun ternyata terbukti salah di graf ini.

Teori graf