삼각형과 사각형
삼각형에서는 모든 두 정점이 직접 연결되므로 세 색이 필요하다. 대각선이 없는 사각형은 두 색을 번갈아 사용하면 되므로 채색수가 2이다. 정점 수와 채색수는 같은 값이 아니다.
완전 그래프
Kₙ에서는 서로 다른 모든 정점 쌍이 연결되어 있어 같은 색을 공유할 수 없다. 따라서 정점이 n개인 완전 그래프의 채색수는 n이다.
이분 그래프
간선이 하나 이상 있는 이분 그래프는 두 부분을 각각 한 색으로 칠할 수 있고 한 색만으로는 간선 양 끝을 구별할 수 없으므로 채색수가 2이다. 정점은 있지만 간선이 전혀 없으면 한 색이면 충분하다.
한 가지 결과로 최소를 단정하지 않는다
어떤 방식으로 네 색을 사용해 칠했다고 채색수가 반드시 4인 것은 아니다. 세 색 이하로 불가능함을 보이거나 더 적은 색칠을 찾아야 한다. 알고리즘이 내놓은 색 수와 정확한 최솟값을 구별한다.
관련 문서
그래프 색칠 / 완전 그래프 / 이분 그래프 / 순환 그래프 / 정점 (그래프 이론) / 간선 (그래프 이론) / 최솟값