This solution guide for CSE 2321 Homework 3 provides formal mathematical proofs and step-by-step solutions for discrete mathematics topics. It covers set theory (power sets and set-builder notation), graph theory (identifying bipartite graphs and Eulerian cycles), and mathematical induction for summation identities.
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.