(The 2021 ICO P4)

The path index of a graph $G$ is the minimum number of paths needed to pass through each vertex of $G$ exactly once. Given a connected graph $G$, what is the maximum possible value for its path index, knowing that the largest set of vertices in $G$ that are pairwise non-adjacent is $n>1$ (independence number)?
Let $P$ be the longest path in $G$ (never passing through the same vertex twice) and $p_{1}, \ldots, p_{l}$ its vertices. We then consider the graph $G_{1}$ obtained by removing the vertices $p_{1}, \ldots, p_{l}$ from $G$, and we repeat: we remove the longest path $P_{1}$, etc. We iterate this process until $G_{k}$ is empty. Let $s_{1}, \ldots, s_{k}$ be the first vertices of $P_{1}, \ldots, P_{k}$. We will show that $p_{1}, p_{l}, s_{1}, \ldots, s_{k}$ have no edges between them. Since $P$ is the longest path in $G$, $p_{1}$ and $p_{l}$ are not connected to any vertex outside of $P$. For the same reason, for all $1 \leqslant i < j \leqslant k$, $s_{i}$ and $s_{j}$ cannot be adjacent because $P_{i}$ is the longest path in the subgraph $G_{i}$. It remains to prove that $p_{1}$ and $p_{l}$ cannot be adjacent. Since $G$ is connected, there exists a vertex $t$ that is not in $P$ and a vertex $p_{i}(2 \leqslant i \leqslant l-1)$ such that $p_{i}$ and $t$ are adjacent. If $p_{1}$ and $p_{l}$ are also adjacent, then we could form a path of length $l+1$ in $G$ with $t p_{i} p_{i-1} \ldots p_{1} p_{l} p_{l-1} \ldots p_{i+1}$. We have thus shown that $p_{1}, p_{l}, s_{1}, \ldots, s_{k}$ are pairwise non-adjacent. The independence number of the graph is $n$, so $k+2 \leqslant n$ and we have removed a total of $k+1 \leqslant n-1$ paths. The path index is therefore at most $n-1$, and we can verify that the maximum is indeed achieved for a graph consisting of a vertex $v$ connected to $n$ other vertices (and no other edges). Then we need to remove the edges one by one (we can remove two at the same time only on the first move).