Petersenov graf: razlika između inačica

Prvi koji ga je nacrtao je [[Alfred Bray Kempe]] [[1886.]] godine. Tada se bavio [[Desargueosove konfiguracije |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 [[Brid (teorija grafova)|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 [[dijametar (teorija grafova)|dijametra]] 2 (isti toliki mu je [[radijus (teorija grafova)|radijus]]) i ujedno najmanji 3-regularan graf [[struk (teorija grafova)|struka]] 5. [[Bridno kromatski broj]] je 4. Ima 10 [[Vrh (teorija grafova)|vrhova]] i 15 [[Brid (teorija grafova)|bridova]]. Sadrži savršeno [[sparivanje (teorija grafova)|sparivanje]]. [[Simetričnost (teorija grafova)|Simetričan]] je pa je [[tranzitivnost (teorija grafova)|tranzitivan]] i po vrhovima i po bridovima. Petersenov graf je najveći (3,2)-[[Mooreov graf]], najmanja najmanja (3,5)-[[rešetka (teorija grafova)|rešetka]], najmanji je [[snark]], [[Kneserov graf]] K(5,2) , sadrži [[minora (teorija grafova)|minore]] <math>K_{5}</math> i <math>K_{3,3}</math>, nije [[planaran graf|planaran]], [[genus (teorija grafova)|genus]] mu je jednak 1 i dr. Protuprimjer je [[Taitov teorem|Taitovom 'teoremu']] u svezi s [[problem četiriju boja|problemom četiriju boja]]: "Svaki 3-regularan graf je 1-faktorabilan". Grupa [[automorfizam grafa|automorfizama]] <math>Aut(P)</math> Petersenova grafa je simetrična grupa <math>S_{5}</math> te je ukupan broj automorfizama jednak 120. Otkriće Petersenova grafa utjecalo je na razvoj različitih grana moderne teorije grafova.<ref name="Majstorović, Boras"/>