A 2 by 2 grid graph. The graph shown in Fig. 6-51 representsa street grid that is 2...

A 2 by 2 grid graph. The graph shown in Fig. 6-51 representsa street grid that is 2 blocks by 2 blocks. (Such a graph iscalled a 2 by 2 grid graph.) For convenience, the vertices arelabeled by type: corner vertices C₁, C₂, C₃, and C₄, boundaryvertices B₁, B₂, B₃, and B₄, and the interior vertex I.

(a) Find a Hamilton path in the graph that starts at I.

(b) Find a Hamilton path in the graph that starts at oneof the corner vertices and ends at a different cornervertex.

(c) Find a Hamilton path that starts at one of the cornervertices and ends at I.

(d) Find (if you can) a Hamilton path that starts at one ofthe corner vertices and ends at one of the boundaryvertices. If this is impossible, explain why.