Petersen graph

Example

The Petersen graph is the graph whose vertices are the $2$-element subsets of $\{1, 2, 3, 4, 5\}$. Two vertices are adjacent if and only if they are disjoint subsets.

It has $\binom{5}{2} = 10$ vertices and $15$ edges, and it is $3$-regular.

Remarks

Its shortest cycle has length $5$. It is not Hamiltonian, and it is not planar. Its chromatic number is $3$, and its edges cannot be coloured with $3$ colours. A common drawing shows it as a pentagon outside, a pentagram inside, and five spokes.

Explanations

L1 human

The Petersen graph is a small graph with $10$ vertices and $15$ edges. It is a standard counterexample: many statements that seem true for all cubic graphs fail for it.