Rozważmy planarny graf \(\displaystyle{ G}\), będący triangulacją.
Czy można w każdym takim grafie znaleźć dwukolorowalny podgraf, który posiadałby wspólną krawędź z każdą ze ścian wyjściowego grafu.
Wiadomo, że nie zawsze istnieje drzewo rozpinające graf \(\displaystyle{ G}\) spełniające tę własność.
Podgraf, którego szukamy może być lasem. Może też zawierać cykle, ale powinny się one znaleźć w oddzielnych kawałkach.
Jeżeli istnieje taki podgraf, to czy jesteśmy w stanie znaleźć jakiś algorytm na jego znajdywanie.