4. (20 points) Paths of Particular Lengths Let G be an undirected graph, and s and t be arbitrary vertices of G. We are interested in the possible lengths of (non necessarily) simple paths from s to t. (a) (10 points). Design an algorithm that determines whether there is a path from s to t with an odd number of edges. Do the same for an even number of edges. Argue that your algorithm is correct and analyze its running time. (b) (10 points). Design an algorithm that determines whether there is a path from s to t whose length is divisible by 3. Argue that your algorithm is correct and analyze its running time. (Hint: It might be useful to also consider paths whose length is 1 or 2 modulo 3). 4. (20 points) Paths of Particular Lengths Let G be an undirected graph, and s and t be arbitrary vertices of G. We are interested in the possible lengths of (non necessarily) simple paths from s to t. (a) (10 points). Design an algorithm that determines whether there is a path from s to t with an odd number of edges. Do the same for an even number of edges. Argue that your algorithm is correct and analyze its running time. (b) (10 points). Design an algorithm that determines whether there is a path from s to t whose length is divisible by 3. Argue that your algorithm is correct and analyze its running time. (Hint: It might be useful to also consider paths whose length is 1 or 2 modulo 3)