Problem 1446

1. Five-Color Theorem Application:
- Given a finite simple planar graph $G$, we start by coloring the vertices of $G$ using the Five-Color Theorem. This theorem states that any planar graph can be colored with at most five colors such that no two adjacent vertices share the same color. Let the colors be $\{1, 2, 3, 4, 5\}$.

2. **Defining the Oriented Graph $G_1$**:
- Construct an oriented graph $G_1$ with vertex set $V(G_1) = \{1, 2, 3, 4, 5\}$ and directed edges as follows:
$$1 \to 2, \quad 1 \to 3, \quad 1 \to 4, \quad 2 \to 3, \quad 2 \to 4, \quad 4 \to 3, \quad 1 \to 5, \quad 5 \to 2, \quad 5 \to 3, \quad 5 \to 4$$

3. **Orienting the Edges of $G$**:
- For each edge $uv \in E(G)$, orient $uv$ as $u \to v$ or $v \to u$ based on the orientation of the corresponding colors in $G_1$. Specifically, if $c(u) \to c(v)$ in $G_1$, then orient $uv$ as $u \to v$; otherwise, orient it as $v \to u$.

4. **Analyzing Cycles in $G$**:
- Consider any cycle in $G$. Suppose the cycle has $k$ edges. We need to show that at most $\frac{3k}{4}$ edges in the cycle share the same orientation.
- Observe that in $G_1$, any path of four edges (e.g., $u_1u_2, u_2u_3, u_3u_4, u_4u_5$) will have at least two edges with different orientations. This is because the directed edges in $G_1$ are arranged such that no four consecutive edges can all have the same orientation.

5. **Conclusion for $G$**:
- Since the orientation of edges in $G$ is derived from $G_1$, the same property holds for $G$. Therefore, in any cycle of $G$, at most $\frac{3k}{4}$ edges can share the same orientation.

6. Optimality of the Bound:
- Consider the complete graph $K_4$. It is a planar graph with 6 edges and 4 vertices. Any orientation of the edges of $K_4$ will have cycles where exactly $\frac{3}{4}$ of the edges share the same orientation. This shows that the bound of $\frac{3}{4}$ is the best possible.

$\blacksquare$