The Petersen graph is the smallest cubic graph that has no Hamiltonian cycle, the smallest cubic graph of girth 5, and the largest cubic graph with diameter 2. It is nonplanar. Although it appears to contain a subgraph homomorphic to K_{5}, it doesn't; however, it *does* contain a subgraph homomorphic to K_{3,3}.

It is named for the Danish mathematician Julius Petersen.