2021 USAMO 第 2 题

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.)

<image>

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?

Planar National Park 是一个无向 3-正则平面图(即所有顶点的度数均为 3)。也就是说：每条路线在两个不同的路口都有两个端点，而每个路口恰好是三个路线的端点。路径仅在交汇处相交(特别是，路径仅在端点处相交)。最后，没有任何路径在相同的两个路口开始和结束。 (下图左侧显示了公园一种可能布局的示例，其中有六个交叉路口和九条小径。)

<图片>

游客按如下方式穿过公园：她从一个顶点开始，沿着一条边行走。当她到达另一个端点时，她向左转。在下一个顶点，她右转，依此类推，在每个顶点交替左转和右转。她这样做，直到回到开始的顶点。在公园所有可能的布局中，她在行走过程中进入任何顶点的最大可能次数是多少？