Graphs are back!
Source: Rioplatense L3 2023 #3
December 6, 2023
combinatorics
Problem Statement
The water city of Platense consists of many platforms and bridges between them. Each bridge connects two platforms and there is not two bridges connecting the same two platforms. The mayor wants to switch some bridges by a series of moves in the following way: if there are three platforms and bridges and (no bridge ), he can switch bridge to a bridge .
A configuration of bridges is good if it is possible to go to any platfom from any platform using only bridges. Starting in a good configuration, prove that the mayor can reach any other good configuration, whose the quantity of bridges is the same, using the allowed moves.