Exercise 2 Show that the following problems are in P (a) 2CNF={ is a satisfiable cnf-formula where each variable appears in at most 2 places } (b) 2SAT={ is a satisfiable cnf-formula where each clause has at most two literals } (c) We are given a map of a city crossed by many rivers. The city is famous for its bridges. We want to know whether it is possible to find a route going through all bridges only once. (d) A coloring of a graph is an assignment of colors to the vertices so that no two neighboring vertices have the same color 2 CoLOR ={GG is colorable with 2 colors. }