One has marked $n$ points on a circle and has drawn a certain number of chords whose endpoints are the marked points. It turned out that the following property is satisfied: whenever any $2021$ drawn chords are removed one can join any two marked points by a broken line composed of some of the remaining drawn chords. Prove that one can remove some of the drawn chords so that at most $2022n$ chords remain and the property described above is preserved.
Problem
Source: Poland 73-3-3
Tags: combinatorics
21.07.2022 19:27
Nice problem! Here's is a sketch of the official solution, which is really nice, and proves that $2022n$ can be changed to $2022(n-1)$. Consider the initial graph $G=G_0$. We first describe the desired set of edges. Take the spanning forest $F_0$ of $G_0$ and remove it to obtain $G_1$, then do the same thing with $G_1$ and $F_1$ and so on, until we obtain $G_{2022}$ and forests $F_0, F_1,..., F_{2021}$. We claim that the union $H$ of those forests, which has at most $2022(n-1)$ edges, works. Suppose $Z$ is a set of $2021$ edges from $H$, and let $H'$ be the graph obtained by removing those edges. We shall prove $H'$ is connected, which we will do by supposing otherwise and finding that if we remove $Z$ from $G$, it won't be connected. Suppose $u$ and $v$ are in different connected components of $H'$. We claim they are in different connected components of $G_{2022}$. Note that proving this will suffice, since there won't be a path between them after deleting the edges in $Z$ from $G$ (there isn't a path neither in $H'$, nor in $G_{2022}$, so the edge between them is in $Z$). We will prove that if $u, v$ are in the same connected component of $G_{2022}$, they are in the same connected component of $H'$. Indeed, note that there exists a path $p_i$ between $u$ and $v$ in each $F_i$, because $u$ and $v$ will be in the same connected component of each $G_i$, so this is true for $F_i$ as well. Thus we have $2022$ paths between $u$ and $v$ in $H$, but $Z$ has $2021$ edges, so some path will be still valid in $H'$, contradiction.
21.07.2022 23:55
I had the same solution as the above official solution a couple months ago when I mocked Polish MO but I never got around to posting it on the thread, seeing @above prompted me to share a bit more on these sorts of results. I think this solution it's pretty motivated and nice. What I wanted to mention is the link below which @TaniniPanini shared with me when I showed him my solution. https://math.stackexchange.com/questions/3330341/number-of-edges-in-a-minimal-k-edge-connected-subgraph A paper by Mader in the above link proves the following two results: Let a $k$ edge-connected subgraph be a graph satisfying the condition with $2022$ replaced by $k$. $\textbf{Result 1:}$ If $|V| \geq k+1$ where $V$ is the number of vertices in $G$ and we denote by $||G||$ the number of edges in the minimum $k$ edge-connected subgraph of $G$, then $$||G|| \leq k \cdot |V| - {k+1 \choose 2}$$ $\textbf{Result 2:}$ If $|V| \geq 3k-2$, then $$||G|| \leq k(n-k)$$which is tight for the complete bipartite graph $K_{k,n-k}$. This specific problem (with $2022n$ replaced by $2022(n-1)$) is also mentioned in the link above and an inductive solution that iteratively takes spanning forests as above is outlined, so this problem is clearly not new, but I think it is not too bad an idea to use unoriginal/old problems in national olympiads, especially when the proof is this nice. Indeed, the following result by Menger also implies this problem immediately: Let $G$ be a finite undirected graph and $x$ and $y$ two distinct vertices. Then the size of the minimum edge cut for $x$ and $y$ (the minimum number of edges whose removal disconnects $x$ and $y$) is equal to the maximum number of pairwise edge-independent paths from $x$ to $y$. Extended to all pairs: a graph is $k$-edge-connected (it remains connected after removing fewer than $k$ edges) if and only if every pair of vertices has $k$ edge-disjoint paths in between. Other than that, this seemed pretty easy for a 3/6 but as I said it's niceness compensates for that.