The answer is $ 5 $. Just case-working

$n$ must be at least 5 because if $n \leq 4$ there is a coloring where all the colored vertices are either in the "top" 4 or in the "bottom" 4. This coloring does not satisfy the given property since a vertex with all neighbors red implies at least 1 color vertex on each of "top" and "bottom". We claim that when $n = 5$, there is always a vertex with all neighbors colored red. By the Pigeonhole Principle, either "top" or "bottom" has at least 3 red vertices. WLOG, say "top" has at least 3 red vertices. It is then easy to work out the cases of 3 & 4 red vertcies to show that there must always be a vertex with all neighbors red. (I would work it out here, but it's hard to explain clearly without drawing a diagram.)

Huh? I color 6 and still unsatisfied the condition. Am I wrong somewhere?

Attachments:

The vertex doesn't have to be red