2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ No, I think it's not proper coloring. I was trying to do it by contradiction, but I'm not sure $\endgroup$
    – learning31
    Nov 16, 2022 at 17:59
  • $\begingroup$ 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$ ? $\endgroup$
    – Balaji sb
    Nov 17, 2022 at 1:39

1 Answer 1

2
$\begingroup$

Assume that colors have numbers 1,2,3,4. Here are some hints.

  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$.

  2. Obviously, there exists an edge whose vertices are colored differently.

  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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .