Διαγαλαξιακή αυτοκρατορία

Στην διαγαλαξιακή αυτοκρατορία υπάρχουν ${10}^{2015}$ πλανήτες, οποιοιδήποτε δύο από τους οποίους συνδέονται με μια κοσμική γραμμή διπλής κατεύθυνσης. Αυτές οι συνδέσεις εξυπηρετούνται από $2015$ μεταφορικές εταιρείες. 

Ο αυτοκράτορας θέλει να κλείσει $k$ από αυτές τις εταιρίες έτσι, ώστε, χρησιμοποιώντας τις υπόλοιπες να μπορεί κάποιος να βρει τρόπο να μεταφερθεί από οποιοδήποτε πλανήτη σε κάποιον άλλο. Για ποιο μέγιστο $k$ με σιγουριά μπορεί να επιτευχθεί ένα τέτοιο πλάνο;

Μαθηματική Ολυμπιάδα Αγίας Πετρούπολης