Petersenov graf, vrsta je grafa iz teorije grafova koji posjeduje niz 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]

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 ${\displaystyle K_{5))$ i ${\displaystyle K_{3,3))$, 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 ${\displaystyle Aut(P)}$ Petersenova grafa je simetrična grupa ${\displaystyle S_{5))$ te je ukupan broj automorfizama jednak 120. Otkriće Petersenova grafa utjecalo je na razvoj različitih grana moderne teorije grafova.^[1]

• Vizingov teorem
• Blanušin graf (Blanušini snarkovi)
• Tutteov graf
• Descartesov snark
• Szekeresov snark
• Cvjetni snarkovi
• Dvostruka zvijezda snark
• Coxeterov graf
• Lovaszova slutnja
• Petersenov teorem
• Bipartitan graf
• Potpun graf
• Haewoodov graf
• McGeeov graf