USAMO 2021 Problem 2

The Planar National Park is a subset of the Euclidean plane consisting of several trails which meet at junctions. Every trail has its two endpoints at two different junctions whereas each junction is the endpoint of exactly three trails. Trails only intersect at junctions (in particular, trails only meet at endpoints). Finally, no trails begin and end at the same two junctions.

A visitor walks through the park as follows: she begins at a junction and starts walking along a trail. At the end of that first trail, she enters a junction and turns left. On the next junction she turns right, and so on, alternating left and right turns at each junction. She does this until she gets back to the junction where she started. What is the largest possible number of times she could have entered any junction during her walk, over all possible layouts of the park?

=========================================

Solution:

The answer is $3$. Let a junction $v$ be endpoint of trails $A$, $B$, and $C$. There are $3\times 2=6$ ways of visiting $v$: $A$ followed by $B$, $A$ followed by $C$, etc. Obviously none of them should be repeated before the visitor stops. Moreover, the following two visits to $v$ before the visitor stops cannot both happen: $A$ followed by $B$ and $B$ followed by $A$. So the maximum number of repeated visits is at most $3$, and it is not hard to construct one.