A 3 by 3 grid graph. The graph shown in Fig. 6-52 represents a street grid that is 3...

A 3 by 3 grid graph. The graph shown in Fig. 6-52 represents a street grid that is 3 blocks by 3 blocks. The graph hasfour corner vertices (C₁, C₂, C₃, and C₄), eight boundary vertices (B₁ through B₈), and four interior vertices (I₁, I₂, I₃,and I₄).

(a) Find a Hamilton circuit in the graph.

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

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

(d) Given any two adjacent vertices of the graph, explainwhy there always is a Hamilton path that starts at oneand ends at the other one.