Rozważamy pewne państwo podzielone na  województw i zawierające  miast. W tym państwie jest  dróg, z których każda łączy jakąś parę miast. Naszym zadaniem jest tak wybrać stolice województw, aby każde województwo miało dokładnie jedną stolicę (będącą jednym z miast tegoż województwa), a każda z dróg miała jakąś stolicę na co najmniej jednym swym końcu. Wiadomo, że każda droga łączy dwa różne miasta, każde województwo zawiera co najmniej jedno miasto, a każde miasto należy do dokładnie jednego województwa.