1. (5 pts) Let A = {1, 2, 3, 6} and B = {2, 3, 5, 6}. Let S be a set, and P ow(S) be the power set of S. (a) What is |P ow(A)|? (b) List the elements of P ow(A). (c) What is |P ow(A ∪ B)|? (d) What is |P ow(A ∩ B)|? (e) List the elements of P ow(A \ B). 2. (10 pts) Let N be the set of natural numbers (including 0). Define the following sets using set builder notation. You should do this in a way that is entirely mathematical, contains no words, and does not rely on recognizing a pattern. For example, if asked to define “The set of natural numbers divisible by 3” then {x ∈ N : x is divisible by 3} or {0, 3, 6, . . .} would not be accepted {x ∈ N : ∃y ∈ N, x ÷ 3 = y} would be accepted (a) The set of even numbers. (b) The set of prime numbers. Recall that 2 is the smallest prime. 3. (10 pts) Define sets A, B, X, Y, Z (i.e. give a specific example) which demonstrate that: (a) B ∪ A ̸= (A \ B) ∪ (B \ A). (b) Z \ (X ∪ Y ) ̸= (Z ∩ X) ∪ (Z ∩ Y ). 4. (10 pts) We say a graph G = (V, E) is bipartite if there are sets V1 ⊆ V and V2 ⊆ V such that all of the following conditions hold: • V1 ∩ V2 = ∅ • V1 ∪ V2 = V • ∀{u, v} ∈ E, [(u ∈ V1 ∧ v ∈ V2) ∨ (v ∈ V1 ∧ u ∈ V2)] 1 Show that the following graph is bipartite by finding V1 and V2 which meet these conditions. Redraw the graph so that V1 is on the left and V2 on the right. 5. (5 pts) Find an Eulerian cycle in this graph and list the vertices in the order visited by the cycle: 6. (10 pts) Using the proof techniques and format guidelines presented in lecture, prove that for all n ≥ 1 the following is true: X n i=1 1 i(i + 1) = n n + 1 . Hint: use the induction proof that Pn i=1 i = n(n+1) 2 as a guide.