„Petersen-gráf” változatai közötti eltérés

A '''Petersen-gráf''' egy nagyon híres,nevezetes speciális gráf. Nagyon gyakran bukkan fel a [[gráfelmélet]]ben különféle állítások ellenpéldájaként. 10 csúcsa és 15 éle van. Bár a névadó [[Julius Petersen]], aki [[1898]]-ban konstruálta meg, ezt a gráfot már 12 évvel Petersen munkája előtt [[1886]]-ban felfedezték.<ref>{{cite journal|author=A. B. Kempe|title=A memoir on the theory of mathematical form|journal=Philosophical Transactions of the Royal Society of London|volume=177|pages=1–70|year=1886}}</ref>

Legyen <math>P=\left\{\ 0,1,2,3,4\right\}\ </math> egy 5 elemű [[halmaz]]. Ebből a <math>P\ </math> halmazból kiválasztjuk az összes kételemű részhalmazt. Ezek száma: <math>{{5}\choose{2}}=10</math>. Ezeket a kételemű halmazokat megfeleltetjük a gráf csúcsainak:

Ez a konstrukció természetesen nem csak 5, hanem más számosságok esetén is működik. ÁtalánosÁltalános esetben az ilymódonily módon konstruált gráfokat [[Kneser-gráf]]oknak nevezzük, tehát a Petersen-gráf egy speciális [[Kneser-gráf]]: <math>KG(5,2)\ </math>.

A Petersen gráf 3 színnel [[gráfok színezése|színezhető]], de kettővel nem (mivel van benne páratlan kör), tehát [[kromatikus szám]]a 3.