2021 USAMO Problems/Problem 2
Problem
The Planar National Park is an undirected 3-regular planar graph (i.e. all vertices have degree 3). That is: 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. (An example of one possible layout of the park is shown to the left below, in which there are six junctions and nine trails.)
A visitor walks through the park as follows: she begins at a vertex and starts walking along an edge. When she reaches the other endpoint, she turns left. On the next vertex, she turns right, and so on, alternating left and right turns at each vertex. She does this until she gets back to the vertex where she started. What is the largest possible number of times she could have entered any vertex during her walk, over all possible layouts of the park?
