CS103 Handout 26

Winter 2018 February 2, 2018

Problem Set 4
This fourth problem set explores set cardinality and graph theory. It serves as tour of the infnite
(through set theory) and the fnite (through graphs and their properties) and will give you a better
sense for how discrete mathematical structures connect across these domains. Plus, you’ll get to see
some pretty pictures and learn about why all this matters in the frst place. ☺
We know you have the midterm coming up on Monday, so we’ve tried to make this checkpoint
problem a lot shorter than the one for PS3. We hope it solidifes the relevant concepts without di-
verting your attention from the exam.
Good luck, and have fun!

Checkpoint due Monday, February 5th at 2:30PM

Remaining problems due Friday, February 9th at 2:30PM
 2/9

Checkpoint Problem: A Really Simple Bijection? (2 Points if Submitted)

Consider the function f : ℕ → ℤ defned as f(n) = n.
i. Prove that f is not a bijection.
Write out the formal defnition of a bijection. If you want to show that f is not a bijection, what do you
need to prove?

Below is a purported proof that f is a bijection:

Theorem: Let f : ℕ → ℤ be defned as f(n) = n. Then f is a bijection.
Proof: In lecture, we proved that |ℕ| = |ℤ|. Since the sets ℕ and ℤ have the same cardinality, we
know that every function between them must be a bijection. In particular, this means that f
must be a bijection, as required. ■
This proof has to be incorrect, since, as you proved in part (i), f isn't a bijection.
ii. What's wrong with this proof? Justify your answer.
Make sure you’re rock-solid on your answer to part (ii) of this problem – what we’ve shown above is a very
common mistake we see people make when writing proofs about cardinality!
 3/9

Problem One: Set Cardinalities

If A and B are sets, the Cartesian product of A and B, denoted A × B, is the set
{ (x, y) | x ∈ A ∧ y ∈ B }.
Intuitively, A × B is the set of all ordered pairs you can make by taking one element from A and one ele-
ment from B, in that order. For example, the set {1, 2} × {u, v, w} is
{ (1, u), (1, v), (1, w), (2, u), (2, v), (2, w) }.
For the purposes of this problem, let’s let ★ and ☺ denote two arbitrary objects where ★ ≠ ☺. Over the
course of this problem, we’re going to ask you to prove that |ℕ × {★, ☺}| = |ℕ|.
i. Draw a picture showing a way to pair of the elements of ℕ × {★, ☺} with the elements of ℕ so
that no elements of either set are uncovered or paired with multiple elements.
You might want to draw some pictures of the set ℕ × {★, ☺} so that you can get a better visual intuition.
ii. Based on the picture you came up with in part (i), defne a bijection f : ℕ × {★, ☺} → ℕ. The in-
puts to this function will be elements of ℕ × {★, ☺}, so you can defne your function by writing
f(n, x) = ________________________
where n ∈ ℕ and x ∈ {★, ☺}.
In defning this function, you cannot assume ★ or ☺ are numbers, since they’re arbitrary values out of your
control. See if you can fnd a way to defne this function that doesn’t treat ★ and ☺ algebraically.
iii. Prove that the function you came up with in part (ii) is a bijection.
The result you’ve proved here essentially shows that 2ℵ₀ = ℵ₀. Isn’t infnity weird?

Problem Two: Understanding Diagonalization

Proofs by diagonalization are tricky and rely on nuanced arguments. In this problem, we'll ask you to re-
view the formal proof of Cantor’s theorem to help you better understand how it works. (Please read the
Guide to Cantor's Theorem before attempting this problem.)
i. Consider the function f : ℕ → ℘(ℕ) defned as f(n) = Ø. Trace through our formal proof of Can-
tor's theorem with this choice of f in mind. In the middle of the argument, the proof defnes some
set D in terms of f. Given that f(n) = Ø, what is that set D? Provide your answer without using
set-builder notation. Is it clear why f(n) ≠ D for any n ∈ ℕ?
Make sure you can determine what the set D is both by using the visual intuition behind Cantor’s theorem
and by symbolically manipulating the formal defnition of D given in the proof.
ii. Let f be the function from part (i). Find a set S ⊆ ℕ such that S ≠ D, but f(n) ≠ S for any n ∈ ℕ.
Justify your answer. This shows that while the diagonalization proof will always fnd some set D
that isn't covered by f, it won't fnd every set with this property.
iii. Repeat part (i) of this problem using the function f : ℕ → ℘(ℕ) defned as
f(n) = { m ∈ ℕ | m ≥ n }
Now what do you get for the set D? Is it clear why f(n) ≠ D for any n ∈ ℕ?
iv. Repeat part (ii) of this problem using the function f from part (iii).
 4/9

Problem Three: Simplifying Cantor's Theorem?

In our proof of Cantor's theorem, we proved that |S| ≠ |℘(S)| by using a diagonal argument. Below is a
purported proof that |S| ≠ |℘(S)| that doesn't use a diagonal argument:
Theorem: If S is a set, then |S| ≠ |℘(S)|.
Proof: Let S be any set and consider the function f : S → ℘(S) defned as f(x) = {x}. To see that
this is a valid function from S to ℘(S), note that for any x ∈ S, we have {x} ⊆ S. Therefore,
{x} ∈ ℘(S) for any x ∈ S, so f is a legal function from S to ℘(S).
Let's now prove that f is injective. Consider any x₁, x₂ ∈ S where f(x1) = f(x₂). We'll prove
that x₁ = x₂. Because f(x₁) = f(x₂), we have {x₁} = {x₂}. Since two sets are equal if and only
if their elements are the same, this means that x₁ = x₂, as required.
However, f is not surjective. Notice that Ø ∈ ℘(S), since Ø ⊆ S for any set S, but that there
is no x such that f(x) = Ø; this is because Ø contains no elements and f(x) always contains
one element. Since f is not surjective, it is not a bijection. Thus |S| ≠ |℘(S)|. ■
Unfortunately, this argument is incorrect. What's wrong with this proof? Justify your answer by pointing
to a specifc claim that’s made here that’s incorrect and explaining why it’s incorrect.

Problem Four: Paradoxical Sets

What happens if we take absolutely everything and throw it into a set? If we do, we would get a set called
the universal set, which we denote �:
� = { x | x exists }
Absolutely everything would belong to this set:
1∈� ℕ∈� CS103 ∈ � whimsy ∈ �
In fact, we'd even have � ∈ �, which is strange but not immediately a problem. Unfortunately, the set �
doesn't actually exist, as its existence would break mathematics.
i. Prove that if A and B are arbitrary sets where A ⊆ B, then |A| ≤ |B|.
Look at the online Guide to Cantor’s Theorem. Formally speaking, if you want to prove that |A| ≤ |B|, what
do you need to prove? Your answer should involve defning some sort of function between A and B and
proving that function has some specifc property or properties.
ii. Using your result from (i), prove that if � exists, then |℘(�)| ≤ |�|.
iii. The Cantor-Bernstein-Schroeder Theorem says that if A and B are sets such that |A| ≤ |B| and
|B| ≤ |A|, then |A| = |B|. Using the Cantor-Bernstein-Schroeder Theorem and the formal defnitions
of the diferent cardinality relations, prove that if A and B are sets where |A| ≤ |B|, then |B| ≮ |A|.
In this proof you’re essentially showing that the ≤ and < relations involving set cardinality work like the ≤
and < relations over regular numbers. Since the goal of the proof is to show that these cardinality relations
work like regular inequality symbols, this result isn’t “obvious” and you’ll need to use formal defnitions.
iv. Using your results from parts (ii) and (iii) of this problem, prove that � does not exist.
The result you've proven shows that there is a collection of objects (the collection of everything that ex-
ists) that cannot be put into a set. When this was discovered at the start of the twentieth century, it led to
a reexamination of logical reasoning itself and a more formal defnition of what objects can and cannot be
gathered into a set. If you're curious to learn more about what came out of that, take Math 161 (Set The-
ory) or Phil 159 (Non-Classical Logic).
 5/9

Problem Five: Independent Sets

An independent set in a graph G = (V, E) is a set I ⊆ V with the following property:
∀u ∈ I. ∀v ∈ I. {u, v} ∉ E.
This question explores independent sets and their properties.
i. Explain what an independent set is in plain English and without making reference to frst-order
logic. No justifcation is necessary.
You may want to draw some pictures of graphs to see what independent sets look like. Don’t just come up
with a literal translation of the frst-order logic formula above; see if you can fnd a simple explanation of
what independent sets are.
ii. Download the starter fles for Problem Set Four from the website, then open the fle GraphTheo-
ry.cpp and implement a function
bool isIndependentSet(Graph G, std::set<Node> I)
that takes as input a graph G and a set I, then returns whether I is an independent set in G. The
defnition of the Graph type is provided in GraphTheory.h.
Our provided starter code contains logic that, given a graph G, fnds the largest independent set in
G by making a lot of repeated calls to isIndependentSet. You might want to look over some of
the sample graphs to get a feel for what large independent sets look like.
iii. You want to conduct a poll for an election and would like to survey people where no two people in
the group know each other so that you can get a good representative sample of the population.
Ideally, you’d fnd a large group of mutual strangers so that your poll has good statistical power.
Explain how you might model this problem in terms of building some sort of graph, then fnding a
large independent set in it. Briefy justify your answer; no formal proof is necessary.
We don’t want you to design an algorithm for fnding large independent sets. Instead, imagine you have a
program that you give as input a graph and that hands back to you an independent set in that graph. What
graph would you give that program as input? What would you do with the output?
The size of an independent set is the number of nodes in it. Formally speaking, if I is an independent set,
then the size of I is given by |I|. The independence number of a graph G, denoted α(G), is the size of the
largest independent set in G. (Note that there can be many diferent independent sets in a graph G that are
all tied for the largest.)
iv. Edit the fle PartA.graph in the res/ directory to defne a graph G where G has exactly fve
nodes and α(G) = 5.
v. Edit the fle PartB.graph in the res/ directory to defne a graph G where G has exactly fve
nodes and α(G) = 1.
A graph can contain multiple diferent independent sets.
vi. Prove or disprove: if G = (V, E) is a graph and I₁ and I₂ are independent sets in G, then I₁ ∩ I₂ is
an independent set in G.
Independent sets are specifed using a defnition given in frst-order logic. Make sure your proof is struc-
tured around that defnition, the same way that proofs of refexivity, symmetry, etc. are structured around
those frst-order defnitions.
 6/9

Problem Six: Vertex Covers

A vertex cover in a graph G = (V, E) is a set C ⊆ V with the following property:
∀u ∈ V. ∀v ∈ V. ({u, v} ∈ E → u ∈ C ∨ v ∈ C).
This question explores vertex covers and their properties.
i. Translate the defnition of a vertex cover into plain English. No justifcation is necessary.
As before, you may want to draw pictures. See if you can fnd an explanation that’s more than just a literal
translation of the above statement.
ii. Implement a function
bool isVertexCover(Graph G, std::set<Node> C)
that takes as input a graph G and a set C, then returns whether C is a vertex cover of G.
Our provided starter code contains logic that, given a graph G, fnds the smallest vertex cover in
G by making a lot of repeated calls to isVertexCover. You might want to explore some of the
sample graphs to get a feel for what vertex covers look like.
iii. Suppose that you have a map of a city's roads and streets (assume that the roads are set up so that
it’s possible to walk between any two points in the city). You want to set up information kiosks so
that no matter where you are, you never need to walk more than a block to get to a kiosk. You
also want to use as few information kiosks as possible to accomplish this. Explain how you might
model this problem by building some sort of graph and looking for a small vertex cover in that
graph. Briefy justify your answer; no formal proof is necessary.
Along the lines of part (iii) of the previous problem, assume you have a black box for fnding small vertex
covers and don’t try to come up with an algorithm on your own. What graph would you hand into that
black box? What would you do with the resulting vertex cover it hands back to you?
The size of a vertex cover is the number of nodes in it. Formally speaking, if C is a vertex cover, then the
size of C is given by |C|. The vertex cover number of a graph G, denoted τ(G), is the size of the smallest
vertex cover of G. (Note that there can be many diferent vertex covers in a graph G that are all tied for
the smallest.)
iv. Edit the fle PartC.graph in the res/ directory to defne a graph G with exactly fve nodes
where τ(G) = 0.
v. Edit the fle PartD.graph in the res/ directory to defne a graph G with exactly fve nodes
where τ(G) = 4.
As with independent sets, graphs can contain multiple diferent vertex covers.
vi. Prove or disprove: if G = (V, E) is a graph and C₁ and C₂ are vertex covers of G, then C₁ ∩ C₂ is a
vertex cover of G.
Vertex covers have some really cool applications. Check out this Numberphile video for one of them!
 7/9

Problem Seven: Chromatic and Clique Numbers

Recall from lecture that a k-vertex coloring of a graph is a way of coloring each node in the graph one of
up to k diferent colors such that no two adjacent nodes are the same color. The chromatic number of a
graph, denoted χ(G), is the minimum value of k for which a k-vertex coloring exists.
i. Implement a function
bool isKVertexColoring(Graph G,
std::map<Node, Color> colors,
std::size_t k);
that takes as input a graph, a mapping from nodes in the graph to colors, and a number k, then re-
turns whether the indicated coloring is a k-vertex coloring. You can assume that the map has one
key for each node in the graph and that the only keys in the map are nodes in G. (The type
std::size_t represents a natural number.)
Our provided starter code contains some logic that, given a graph G, fnds a minimum k-vertex-
coloring of G by making a lot of calls to your isKVertexColoring function. We recommend tak-
ing some time to look at a few sample graphs and their minimum colorings – they’re quite pretty!
Here’s a new defnition. A clique in a graph G = (V, E) is a set K ⊆ V with the following property:
∀u ∈ K. ∀v ∈ K. (u ≠ v → {u, v} ∈ E).
This question explores the connection between cliques and chromatic numbers.
ii. Translate the defnition of a clique into plain English. No justifcation is necessary.
iii. Implement a function
bool isClique(Graph G, std::set<Node> K)
that takes as input a graph G and a set K, then returns whether K is a clique in G.
Our provided starter code contains some logic that, given a graph G, fnds the largest clique in G
by making a lot of calls to your isClique function. You may want to take a look at some of the
provided sample graphs to see what large cliques look like.

(We will cover the material necessary to solve the remainder of this problem in Monday’s lecture.)

The size of a clique K, denoted |K|, is the number of nodes in K. The clique number of a graph, denoted
ω(G), is the size of the largest clique in G. (Note that there can be many diferent cliques in a graph G
that are all tied for the largest.)
iv. Prove that if G is a graph, then χ(G) ≥ ω(G).
We’re expecting you to write a formal proof here. It may be easiest to do this by contradiction.
v. Edit the fle PartE.graph in the res/ directory to contain a graph G where χ(G) ≠ ω(G). This
shows that, in general, the chromatic and clique numbers of a graph don’t have to be equal.
Aim to fnd the smallest example that you can. Although you aren’t required to submit the simplest example
possible and we aren’t asking for an explanation as to why your answer is correct, you should not feel satis-
fed with your answer unless you can justify why it’s got to be the simplest answer possible.
 8/9

Problem Eight: Chromatic and Independence Numbers

(We will cover the material necessary to solve this problem in Monday’s lecture.)
In Problem Seven, you explored the connection between clique numbers and chromatic numbers. This
problem explores the connection between independence numbers and chromatic numbers.
Let n be an arbitrary positive natural number. Prove that if G is an arbitrary undirected graph with exactly
n2+1 nodes, then χ(G) ≥ n+1 or α(G) ≥ n+1 (or both).
You should defnitely check out what the Guide to Proofs on Discrete Structures says to do if you want to
prove a statement of the form P ∨ Q, since it’ll make this proof a lot easier to write!

Problem Nine: Bipartite Graphs

An undirected graph G = (V, E) is called a bipartite graph if there exist two sets V₁ and V₂ such that
• every node v ∈ V belongs to exactly one of V₁ and V₂, and
• every edge e ∈ E has one endpoint in V₁ and the other in V₂.
The sets V₁ and V₂ here are called bipartite classes of G. To help you get a better intuition for bipartite
graphs, suppose that you have a group of people and a list of restaurants. You can illustrate which people
like which restaurants by constructing a bipartite graph where V₁ is the set of people, V₂ is the set of
restaurants, and there's an edge from a person p to a restaurant r if person p likes restaurant r.
Bipartite graphs have many interesting properties. One of the most fundamental is this one:
An undirected graph is bipartite if and only if it contains no cycles of odd length.
Intuitively, a bipartite graph contains no odd-length cycles because cycles alternate between the two
groups V₁ and V₂, so any cycle has to have even length. The trickier step is proving that if G is a graph
that contains no cycles of odd length, then G has to be bipartite. For now, assume that G has just one con-
nected component; if G has multiple connected components, we can treat each one as a separate graph for
the purposes of determining whether G is bipartite. (You don't need to prove this, but I'd recommend tak-
ing a minute to check why this is the case.)
Suppose G is a connected, undirected graph with no cycles of odd length. Choose any node v ∈ V. Let V₁
be the set of all nodes that are connected to v by a path of odd length and V₂ be the set of all nodes con-
nected to v by a path of even length. (Note that these paths do not have to be simple paths.) Formally:
V₁ = { x ∈ V | there is an odd-length path from v to x }
V₂ = { x ∈ V | there is an even-length path from v to x }
i. Prove that V₁ and V₂ have no nodes in common.
Remember that there might be multiple diferent paths of diferent lengths from v to some other node x, so
be careful not to talk about “the” path between v and x. Also note that these don’t have to be simple paths.
ii. Using your result from part (i), prove that G is bipartite.
What do you need to show to prove that every node belongs to one of exactly two sets? Make sure you can
point out how you are using the fact that G is connected and the fact that G has no cycles of odd length.
 9/9

Optional Fun Problem 1: Hugs All Around! (1 Point Extra Credit)

There's a party with 137 attendees. Each person is either honest, meaning that they always tell the truth,
or mischievous, meaning that they never tell the truth. After everything winds down, everyone is asked
how many honest people they hugged at the party. Surprisingly, each of the numbers 0, 1, 2, 3..., and 136
was given as an answer exactly once.
How many honest people were at the party? Prove that your answer is correct and that no other answer
could be correct.

Optional Fun Problem 2: How Many Functions Are There? (1 Point Extra Credit)
If A and B are sets, we can defne the set BA to be the set of all functions from A to B. Formally speaking:
BA = { f | f : A → B }
Prove that |ℕ| < |ℕℕ|. This shows that ℵ₀ < ℵ₀ℵ₀. Isn’t infnity weird?