Stroll on the graph
Source: 239 2012 J6
July 30, 2020
combinatorics
Problem Statement
Let be a planar graph all of whose vertices are of degree . Vasya and Petya walk along its edges. The first time each of them goes as he pleases, and then each of them goes straight (from the three roads they have to choose the middle one). As the result, each vertex was visited by exactly one of them and exactly once. Prove that this graph has an even number of vertices.