I am trying to prove that if G is a 2-connected graph of order 4 or more such that each vertex of G is colored with one of the four colors red, blue, green, and yellow and each color is assigned to at least one vertex of G, then there exists a path containing at least one vertex of each of the four colors.
Could anyone help me out?
Assume that colors have numbers 1,2,3,4. Here are some hints.
It is known that for any three vertices $x,y,z$ of a $2$-connected graph there exists a $xy$-path passing through $z$.
Obviously, there exists an edge whose vertices are colored differently.
Choose an edge $ux$ ($u,x\in V(G)$) whose vertices are colored 3 and 4. Let the vertex $x$ have color 3 and let $y$ and $z$ be arbitrary vertices of colors 1 and 2. It follows from (1) that there exists a $xy$-path $P$ passing through $z$.
If $u\in P$, then the path $P$ contains vertices of each of the 4 colors, if $u\not\in P$, then the sought path is $uP$.