The "Green Path Problem": Given a graph G on n vertices with n/2 green vertices and n/2 red vertices (n is even), is there a path from V_1 to v_n which contains every green vertex but passes through no vertex more than once? Show that the Green Path Problem is NP-complete. The "Green Path Problem": Given a graph G on n vertices with n/2 green vertices and n/2 red vertices (n is even), is there a path from V_1 to v_n which contains every green vertex but passes through no vertex more than once? Show that the Green Path Problem is NP-complete