3. Recall that as we discussed in class, there is no known fast algorithm for graph

isomorphism, and it is believed that no such algorithm exists. However, it is often possible to

solve graph isomorphism quickly if there are restrictions on the types of graphs allowed as input.

Your best friend Fred has a proposal for an alternative graph isomorphism algorithm when the

input graphs are restricted to be trees. He suggests the following:

1) For each vertex v in G₁, compute deg(v) and append this value to a list L₁.

2) For each vertex v in G₂, compute deg(v) and append this value to a list L2.

3) Sort the lists L₁ and L2 in increasing order.

4) If L₁ and L₂ are the same, reutrn "yes", otherwise return "no”.

Does Fred's algorithm work on all possible inputs? You can assume the input graphs are both

trees. Prove your answer is correct.