Let $ABCD A'B'C'D'$ be a cube. Coloring red the four vertices of a face (e.g. $A, B, C, D$), no vertex of the cube has all three adjacent vertices colored red, so $n \ge 5$.

Now, let us color 5 vertices of the cube in red. Anyway we do it, one of the faces $ABCD$ and $A'B'C'D'$ has at least three red vertices. Without loss of generality, suppose $A, B, C$ are red.

If $D$ is also red, the face $A'B'C'D'$ has only one red vertex; if $X'$ is the red vertex, with $X \in \{A, B, C, D\}$, then all the adjacent vertices of $X$ are colored red.

If $D$ is not red, the face $A'B'C'D'$ has two red vertices. If one of $B'$ or $D'$ is red, then the adjacent vertices of $B$, respectively $D$, are all red. Otherwise, $A'$ and $C'$ are red.