Problem 4. (15 marks) Given an undirected graph G = (V,E), the square of it is the graph such that for any two nodes , if and only if the distance between u and v in G is at most 2, i.e., or there is a such that . (Therefore, it is clear that any will remain an edge also in .)

a. (7 marks) Propose an algorithm that takes as an input a graph G with a max-degree of in the adjacency list model and outputs in , and prove the running time of your algorithm.

b. (8 marks) Propose an algorithm that takes as an input a graph G in the adjacency matrix model and outputs G2 in . Prove the correctness and running time of your algorithm. (Hint: We call it an adjacency matrix for a reason...)

2 = { , 2 )