Graf Petersena

Graf Petersena – w teorii grafów, szczególny graf kubiczny o 10 wierzchołkach i 15 krawędziach. Nazwany na cześć matematyka Juliusa Petersena, który w 1898 podał go jako przykład grafu regularnego stopnia 3 bez mostów, którego krawędzi nie można pokolorować trzema kolorami.

• 
  Graf Petersena
• 
  Graf Petersena narysowany z dwoma przecięciami.
• 
  Graf Petersena narysowany tak, że wszystkie krawędzie są tej samej długości.

Własności

Graf Petersena...

• jest silnie regularny stopnia 3.
• jest trójspójny i trójspójny krawędziowo.
• ma ścieżkę Hamiltona, ale nie ma cyklu Hamiltona.
• jest grafem trójdzielnym.
• jest dopełnieniem grafu krawędziowego grafu K₅.
• jest symetryczny, to znaczy krawędziowo tranzytywny i wierzchołkowo tranzytywny.
• nie jest grafem planarnym.

Własności grafu Petersena:

Przypisy

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Petersen Graph, [w:] MathWorld, Wolfram Research [dostęp 2024-04-28]  (ang.).
• Petersen graph (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2025-12-14].