Remember to explain your solutions clearly. A formula is not a complete solution, even if correct.

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 2Color = {G | G is colorable with 2 colors.}