Let $G=(V,E)$ be a simple directed graph that every arrow is colored with black or pink. If $G$ has monochromatic cycle then $G$ has a simple monochromatic cycle. How to prove that theorem?
monochromatic cycle is a cycle which is colored with one color only.
How should I prove this theorem?
I have a hinche that we need to look at the subpath of the cycle and find out that it's also a simple cycle (but how). In that way we will get a monochromatic simple cycle because its a subpath of the monochromatic cycle.
Suppose the cycle visits some intermediate vertex more than once. If we omit the portion of the path between the first and second visit, we still have a monochromatic cycle, but it's shorter than the original one.
From this observation, you should have no trouble constructing a proof.