2023 IMO Shortlist C7

The Imomi archipelago consists of $n \geq 2$ islands. Between each pair of distinct islands is a unique ferry line that runs in both directions, and each ferry line is operated by one of $k$ companies. It is known that if any one of the $k$ companies closes all its ferry lines, then it becomes impossible for a traveller, no matter where the traveller starts at, to visit all the islands exactly once (in particular, not returning to the island the traveller started at). Determine the maximal possible value of $k$ in terms of $n$. (Ukraine)

伊莫米群岛由 $n \geq 2$ 个岛屿组成。每对不同的岛屿之间都有一条双向运行的独特渡轮线路，每条渡轮线路均由 $k$ 公司之一运营。众所周知，如果任何一家 $k$ 公司关闭其所有渡轮线路，那么无论旅行者从哪里出发，都不可能一次性访问所有岛屿(特别是不返回旅行者出发的岛屿)。根据 $n$ 确定 $k$ 的最大可能值。 (乌克兰)