반대 그래프를 직접 생각하면 조건이 복잡해 보일 수 있다. 원래 그래프에서 두 정점 의 관계를 기준으로 조건을 다시 쓰자.
반대 그래프에서 간선으로 연결된 두 정점은 서로 다른 색이어야 한다. 이는 원래 그래프에서 간선으로 연결되어 있지 않은 두 정점은 서로 다른 색이어야 한다는 뜻이다.
반대 그래프에서 간선으로 연결되어 있지 않은 두 정점은 서로 같은 색이어야 한다. 이는 원래 그래프에서 간선으로 연결된 두 정점은 서로 같은 색이어야 한다는 뜻이다.
따라서 원래 그래프에서는 다음 조건이 성립해야 한다.
이 조건으로부터, 같은 연결 요소 안의 모든 정점은 같은 색이어야 한다. 왜냐하면 간선을 따라 이동할 때마다 색이 같아야 하기 때문이다.
또한 같은 색을 가진 두 정점은 반드시 간선으로 연결되어 있어야 한다. 그러므로 각 연결 요소는 완전 그래프여야 한다.
결국 조건은 다음과 동치이다.
연결 요소는 DSU 또는 DFS/BFS로 구할 수 있다. 어떤 연결 요소의 크기가 라면, 그 연결 요소가 완전 그래프이기 위한 필요충분조건은 그 안의 모든 정점의 차수가 정확히 인 것이다.
따라서 모든 간선을 DSU로 합친 뒤, 각 연결 요소의 크기를 구한다. 연결 요소가 개보다 많으면 불가능하다. 그렇지 않다면 각 정점 에 대해
인지 확인한다. 모든 정점이 이 조건을 만족하면 가능하고, 각 연결 요소에 서로 다른 색을 배정하면 된다.
시간 복잡도는 이고, 메모리 사용량은 이다.
