Vrijeme: 19:33

Ekstremalni grafovi #2

U jednoj državi postoji 78 otoka, a između svakih dvaju otoka postoji točno jedna direktna dvosmjerna brodska linija. Svaka linija pripada jednoj od dviju brodskih kompanija. Koji je najmanji mogući prirodan broj d takav da je uvijek moguće tvrditi sljedeće: Postoji kompanija takva da ako koristimo samo linije te kompanije, možemo od bilo kojeg grada doći do bilo kojeg drugog koristeći najviše d linija?