I teach a fairly advanced algorithms class to high schoolers and I accidentally presented them with a bunk reduction from Hamiltonian path to the Tripartite graph decision problem. Is there a simple-ish reduction that I can show them to correct my mistake, or do I have to go through SAT or something like that?
My attempt involved creating three vertices in the transformed input G’ for every one vertex in the original graph G and connecting them sparsely (for an edge (u, v) in G, I was creating (u1, v2), (u2, v3), and (u3, v1) in G’). This obviously doesn’t work for several reasons that I did not realize because it worked on two examples and I was tired. Particularly, if a vertex has degree >=3 in G, then this transformation will always cause the tripartite algorithm to answer false regardless of if G has a Hamiltonian path.