Pruning a highly connected graph

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Pruning a highly connected graph

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Poland 73-3-3

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

224 posts

#1 h Mar 31, 2022, 10:51 PM

Y by

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.

This post has been edited 1 time. Last edited by timon92, Mar 31, 2022, 11:08 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1385 posts

#2 h Jul 21, 2022, 4:27 PM

Y by

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.

This post has been edited 1 time. Last edited by VicKmath7, Jul 21, 2022, 4:28 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

277 posts

#3 h Jul 21, 2022, 8:55 PM

Y by

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.

This post has been edited 3 times. Last edited by bora_olmez, Jul 22, 2022, 7:44 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a