Exercise 4 (Aperiodicity of RW on graphs). Let (Xro be a random walk on a connected graph G- (V, E) (i) Show that all nodes have the same period. (i) If G contains an odd cycle C (e.g., triangle), show that all nodes in C have period (iii) Show that X, is aperiodic if and only if G contains an odd cycle. (iv)* (Optional) Show that X, is periodic if and only if G is bipartite. (A graph G is bipartite if there exists a partition V- Au B of nodes such that all edges are between A and B.)