El grafo de Petersen lleva el nombre de Julius Petersen, quien en 1898 lo construyó para ser el grafo cúbico sin puentes más pequeño que no se puede 3-colorear.

La representación planar simétrica más común del grafo de Petersen (como un pentagrama contenido en un pentágono) se cruza cinco veces.

Sin embargo, esta no es la mejor representación para ahorrar cruces; existe otra representación (la expuesta en la imagen siguiente) con tan sólo dos cruces.

La superficie no orientable más simple en la cual el grafo de Petersen puede ser incrustado es el plano proyectivo.

En concreto, es 3-arco-transitivo: todo camino dirigido de tres aristas en el grafo de Petersen puede ser transformado en cualquier otro camino similar por una simetría del grafo.

Todo homomorfismo del grafo de Petersen a sí mismo que no identifica vértices adyacentes es un automorfismo.

Es el grafo vértice-transitivo más pequeño que no es un grupo de Cayley.

Es hipoamiltoniano, lo que significa que aunque no tiene un ciclo hamiltoniano, al eliminar cualquier vértice se convierte en hamiltoniano, y es el grafo hipoamiltoniano más pequeño.

Si hay un ciclo hamiltoniano, se debe elegir un número par de estos bordes.

Si sólo se eligen dos de ellos, sus vértices finales deben estar adyacentes en los dos 5 ciclos, lo que no es posible.

Supongamos que no se elige el borde superior del corte (todos los demás casos son iguales por simetría).

Es el snark más pequeño posible, y fue el único conocido desde 1898 hasta 1946.

El teorema del snark, conjeturado por W. T. Tutte y anunciado en 2001 por Robertson, Sanders, Seymour y Thomas, afirma que cada snark tiene el grafo de Petersen como un menor.

El grafo de Petersen requiere al menos tres colores en cualquier coloración que rompa todas sus simetrías; es decir, su número distintivo es tres.

Según DeVos, Nesetril y Raspaud, "Un ciclo de un grafo G es un conjunto C

La familia de Petersen está formada por los siete grafos que pueden ser formados a partir del grafo Petersen por cero o más aplicaciones de transformaciones Δ-Y o Y-Δ.