Petersenov graf, vrsta grafa iz teorije grafova. je malen graf sa nizom posebnih svojstava koja ga svrstavaju u jedno od ključnih otkrića na području teorije grafova. Nazvan je po Juliusu Petersenu koji je 1898. godine ustanovio da je baš ovaj najmanji 3-regularan graf bez mostova koji nije 3-bridno obojiv. [1]
Osobine
Prvi koji ga je nacrtao je Alfred Bray Kempe 1886. godine. Tada se bavio Desargueosovim konfiguracijama. Vrhovi mu predstavljaju 10 pravaca Desargueosovih konfiguracija, a bridovi reprezentiraju parove pravaca koji se ne sijeku niti u jednoj od 10 točaka konfiguracije. Graf je 3-povezan i 3-bridno povezan. Jednostavan je i najmanji 3-regularan graf bez reznih bridova koji nema Hamiltonov ciklus, najmanji hipohamiltonov graf, najmanji 3-regularan graf bez reznih bridova čiji bridno kromatski broj iznosi 4 te najveći 3-regularan graf dijametra 2 (isti toliki mu je radijus) i ujedno najmanji 3-regularan graf struka 5. Bridno kromatski broj je 4. Ima 10 vrhova i 15 bridova. Sadrži savršeno sparivanje. Simetričan je pa je tranzitivan i po vrhovima i po bridovima. Petersenov graf je najveći (3,2)-Mooreov graf, najmanja najmanja (3,5)-rešetka, najmanji je snark, Kneserov graf K(5,2) , sadrži minore i , nije planaran, genus mu je jednak 1 i dr. Protuprimjer je Taitovom 'teoremu' u svezi s problemom četiriju boja: "Svaki 3-regularan graf je 1-faktorabilan". Grupa automorfizama Petersenova grafa je simetrična grupa te je ukupan broj automorfizama jednak 120. Otkriće Petersenova grafa utjecalo je na razvoj različitih grana moderne teorije grafova.[1]
