Quando dispomos de apenas duas cores, o problema da coloração dos vértices de um grafo não-dirigido é simples. O algoritmo que resolve a bicoloração é útil e importante.
Um grafo não-dirigido é bicromático (ou bipartido) se admite uma coloração dos vértices com não mais que 2 cores. (Grafos bicromáticos são usualmente desenhados de modo que os vértices de uma das cores fiquem alinhados na parte superior da figura e os da outra cor fiquem alinhados na parte inferior.)
Para provar que um grafo é bicromático, basta exibir uma bicoloração dos vértices. Mas como é possível provar que um grafo não é bicromático? É óbvio que um grafo dotado de circuito de comprimento ímpar (ou seja, comprimento 1, ou 3, ou 5, etc.) não é bicromático. É menos óbvio (mas não menos verdade) que a vale a recíproca: todo grafo não-bicromático tem um circuito ímpar. Resumindo:
Teorema: Um grafo é bicromático se e somente se não tem circuito de comprimento ímpar.