Rys. 1 Dla powyższego planu Bitlandii, jeśli armia zaczyna w mieście 1, to generał A może przesunąć ją do miasta 3, 4 lub 5. Niezależnie od jego wyboru generałowi B pozostaje jedyny ruch do miasta 2. Generał A rusza wtedy do jeszcze nieodwiedzonego miasta ze zbioru i wygrywa. Jeśli armia zaczyna w mieście 3, to wygra generał B.

Plan Bitlandii możemy traktować jako graf nieskierowany  o   wierzchołkach i   krawędziach. Na początek spróbujmy rozwiązać prostszą wersję tego zadania, w której graf  jest dwudzielny (wierzchołki reprezentujące miasta możemy podzielić na dwa zbiory  tak, że każda krawędź-droga łączy wierzchołki znajdujące się w różnych zbiorach). Niech miasto początkowe będzie w   W tej sytuacji ruch generała A zawsze prowadzi z   do  zaś ruch generała B – przeciwnie. Rozważmy pewną rozgrywkę między generałami, w której zwycięża generał A oraz wszystkie miasta Bitlandii zostały odwiedzone. W rozgrywce tej dla każdego miasta  generał A wybrał pewne miasto  do którego ruszył się z   Z warunków zadania wynika, że funkcja  jest bijekcją. Ponadto, zbiór krawędzi, którymi poruszał się generał A, jest doskonałym skojarzeniem w grafie

Zauważmy więc, że jeśli w grafie  istnieje doskonałe skojarzenie  to generał A wygrywa, startując z dowolnego miasta, a jego strategia polega na poruszaniu się po krawędziach ze skojarzenia  Generał B nigdy nie będzie mógł zrobić ruchu krawędzią z 

Rys. 2 Ilustracja przypadku dla Krawędzie należące do są pogrubione.

No dobrze, ale co w przypadku, gdy w   nie istnieje doskonałe skojarzenie? Niech  będzie pewnym najliczniejszym skojarzeniem w   zaś  będzie wierzchołkiem początkowym, który nie jest skojarzony w   Zauważmy, że jakikolwiek ruch generała A musi prowadzić do wierzchołka  który jest skojarzony w   inaczej bowiem moglibyśmy powiększyć  dokładając do niego krawędź  Generał B może wtedy odpowiedzieć ruchem wzdłuż krawędzi z   Okazuje się, że będzie mógł tak zrobić zawsze. Załóżmy bowiem, że w  -tym ruchu generał B trafia na nieskojarzony wierzchołek, czyli  jest ciągiem odwiedzonych wierzchołków,  wtedy gdy  jest parzyste, oraz  i   są nieskojarzone w  (Rys. 2). Wówczas możemy usunąć ze skojarzenia  krawędzi  dla  parzystego, a zamiast tego dołożyć  krawędzi  dla  nieparzystego, co daje skojarzenie liczniejsze niż – sprzeczność. Wynika z tego, że jeśli w grafie  pewne najliczniejsze skojarzenie nie kojarzy wierzchołka początkowego, to skojarzenie to wyznacza strategię wygrywającą dla generała B.

Pozostał do rozważenia przypadek, w którym wierzchołek początkowy  jest skojarzony w każdym najliczniejszym skojarzeniu. Niech  będzie pewnym takim skojarzeniem. Pokażemy, że wygrywa generał A, a jego strategią jest poruszanie się wzdłuż krawędzi skojarzenia  Argument jest podobny jak poprzednio: gdyby w pewnym momencie dla ciągu odwiedzonych wierzchołków  wierzchołek  był nieskojarzony w   to wymieniając  krawędzi  dla  nieparzystego na  krawędzi  dla  parzystego, dostajemy nowe skojarzenie (równoliczne z   a więc o największej liczności), które nie kojarzy wierzchołka  Znów dochodzimy do sprzeczności.

Wystarczy zatem dla każdego wierzchołka  sprawdzić, czy każde najliczniejsze skojarzenie kojarzy ten wierzchołek. Dowolne najliczniejsze skojarzenie  możemy wyznaczyć np. w czasie  poprzez -krotne wyszukanie ścieżki powiększającej. Wierzchołek  jest kojarzony w każdym najliczniejszym skojarzeniu, jeśli jest skojarzony w   oraz, po usunięciu  z grafu, liczność najliczniejszego skojarzenia się zmniejsza. Zauważmy, że szukając skojarzenia, nie musimy zaczynać zawsze od nowa, wystarczy w skojarzeniu  usunąć krawędź kojarzącą  oraz poszukać jednej ścieżki powiększającej. Zatem cały algorytm działa w czasie

W tym momencie Czytelnik może pokręcić z powątpiewaniem głową, że, owszem, zrobiliśmy rozgrzewkę i rozwiązaliśmy zadanie dla grafów dwudzielnych – ale jak nasze rozważania mają się do rozwiązania dla grafów dowolnych? I będzie miał słuszność, gdyż w istocie wiele problemów, które umiemy sprawnie rozwiązać dla grafów dwudzielnych, staje się trudne dla grafów niemających tej własności. Zachęcam jednak Czytelnika do przeczytania jeszcze raz powyższego rozwiązania i przekonania się, że tak naprawdę nigdzie nie korzystamy z założenia, że graf  jest dwudzielny. Zatem nasze rozwiązanie działa również w ogólnym przypadku, pod warunkiem że umiemy znajdować najliczniejsze skojarzenia w dowolnych grafach. Można to zrobić w czasie  algorytmem Edmondsa i w takim też czasie działa całe rozwiązanie.