Jelöljük a piros színű országok számát $n$-nel, és csúcsaik számát valamilyen sorrendben $p_1$-gyel, $p_2$-vel, $\text{...}$, $p_n$-nel. A megfelelő számokat a kék színű országokra jelölje $m$ és $k_1$, $k_2$, $\text{...}$, $k_m$. A $P=p_1+p_2+\text{...}+p_n$ összeg aszerint páros vagy páratlan, hogy a páratlan csúcsú, piros színű országok száma páros-e, vagy sem. Ugyanígy $K=k_1+k_2+\text{...}+k_m$ paritása megegyezik a páratlan csúcsú, kék színű országok számának a paritásával, állításunk tehát azt jelenti, hogy $P+K$ páros.
Tegyük fel, hogy a piros és kék országok kiküldenek a hozzájuk tartozó csúcsokhoz egy‐egy katonát. Összesen $P+K$ katonát küldenek ki, állításunkat tehát belátjuk, ha sikerül ezeket a katonákat párba állítani. Egy‐egy csúcshoz legfeljebb két katona érkezik, hiszen a csúccsal szomszédos országok között legalább az egyik a sárga és a zöld országok közül való. Ha egy csúcsban két katona őrködik, akkor azok alkossanak egy párt. Az olyan csúcsokban, amelyekben csak egy katona van, a katona országán kívül még van egy sárga és egy zöld ország. Menjünk el ezek közös határvonalán a szomszédos csúcsig: itt is egy magányos katona áll, legyen ez az előbbi párja. Ez a párosítás nyilván kölcsönös, hiszen az utóbb talált katonától épp az előbbihez ment a zöld és sárga országok közt futó határvonal, állításunkat ezzel beláttuk.