# Graph connected, exists a path containing at least one vertex of each of the four colors.

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?

• No, I think it's not proper coloring. I was trying to do it by contradiction, but I'm not sure Nov 16, 2022 at 17:59
• If the entire graph is a cycle with $x,y$ in the cycle colored with colors 1,2 and vertices in left path of $xy$ of the cycle is colored with color 3 and the vertices in right path of $xy$ the cycle colored with color 4, will it satisfy ur theorem ? So is ur question , some arbitrary path without fixing end points $x,y$ ? Nov 17, 2022 at 1:39

1. It is known that for any three vertices $$x,y,z$$ of a $$2$$-connected graph there exists a $$xy$$-path passing through $$z$$.
3. 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$$.
4. 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$$.