Vrijeme: 22:06

Ekstremalni grafovi #4

U nekoj državi postoji 128 gradova, a između nekih parova gradova prometuju direktne dvosmjerne avionske linije (najviše jedna linija između svaka dva grada), pri čemu svaka linija pripada jednoj od dviju kompanija. Odredi najmanji prirodan broj m takav da vrijedi sljedeće: Ako ukupno postoji barem m avionskih linija, sigurno je moguće napraviti kružno putovanje koje posjećuje točno 3 ili 5 gradova, a koristi linije samo jedne kompanije.