Giả sử ta bắt đầu với một node bất kỳ với màu đỏ, ta có thể tham lam nếu như cạnh nối với node đó là lẻ thì đầu mút còn lại sẽ tô màu đen, ngược lại sẽ là màu đỏ. Thực hiện như vậy đến khi ~DFS~ toàn bộ cây.

Độ phức tạp: ~O(n)~