Problem 1434

1. Euler's Theorem Application:
By Euler's formula for planar graphs, we have:
$$v - e + f = 2$$
where $v$ is the number of vertices, $e$ is the number of edges, and $f$ is the number of faces.

2. Triangulation Assumption:
Assume that all faces of the graph are triangles. This is possible for $n \geq 3$. In this case, each face has 3 edges, and each edge belongs to exactly 2 faces. Therefore:
$$3f = 2e$$
Substituting this into Euler's formula, we get:
$$v - e + \frac{2e}{3} = 2 \implies 3v - 3e + 2e = 6 \implies 3v - e = 6 \implies e = 3v - 6$$

3. Definition of Good and Bad Vertices:
Define a vertex $v$ as "good" if, when we go around $v$ through a complete cycle, the edges with the endpoint at $v$ change their color at most two times. Otherwise, the vertex is "bad".

4. Counting Bad Vertices:
Let the number of bad vertices be $k$. For a vertex to be bad, the edges around it must change color at least three times. This means there are at least 3 color changes around each bad vertex.

5. Counting Color Changes:
Let $c$ be the total number of color changes in the graph. Each color change is counted twice (once for each vertex it involves), so:
$$2c \geq 3k$$

6. Relating Color Changes to Faces:
Since each face is a triangle and each triangle has 3 edges, the total number of edges is related to the number of faces by:
$$2f = 4v - 8$$
Therefore:
$$2c \leq 2f = 4v - 8$$

7. Combining Inequalities:
Combining the inequalities, we get:
$$3k \leq 2c \leq 4v - 8 \implies k \leq \frac{4v - 8}{3}$$
Since $k$ must be an integer, we can simplify this to:
$$k \leq v - 2$$

8. Conclusion:
Since $k \leq v - 2$, there are at most $v - 2$ bad vertices. Therefore, there must be at least 2 good vertices in the graph.

$\blacksquare$