5. HC: Graph G has circuit that begins and ends at v1, visiting each vertex once.

HP: Graph G has a path that visits each vertex exactly once (begin anywhere, end anywhere)

a. Give yes and no instances of HC and HP

b. Prove or disprove: the following is a polynomial reduction from HC to HP

Given an undirected graph G=(V,E), create a new graph G by adding one new vertex s and |V| new edges, connecting s to every vertex in the original G.