Bài toán tô màu đồ thị:

2 màu

1 màu

Tô màu cho các đỉnh của đồ thị sao cho số màu được dùng là ít nhất và 2 đỉnh kề nhau (có cung nối) không được tô cùng 1 màu. Với đồ thị sau ta có thể tô tối thiểu bao nhiêu màu:

3 màu

4 màu