MathDB

Removing Edges for Connected Subgraph

Source: St. Petersburg Mathematical Olympiad 2015 9.6

February 25, 2016

combinatoricsgraph theoryColoring

Problem Statement

There are

10^{2015}

planets in an Intergalactic empire. Every two planets are connected by a two-way space line served by one of

2015

travel companies. The Emperor would like to close

k

of these companies such that it is still possible to reach any planet from any other planet. Find the maximum value of

k

for which this is always possible.
(D. Karpov)