CS 70 Discrete Mathematics and Probability Theory
Fall 2021 HW 3
Due: Friday 9/17, 10:00 PM
Grace period until Friday 9/17 11:59 PM
Sundry
Before you start writing your final homework submission, state briefly how you worked on it. Who
else did you work with? List names and email addresses. (In case of homework party, you can just
describe the group.)
1 Graph Basics
In the first few parts, you will be answering questions on the following graph G.
(a) What are the vertex and edge sets V and E for graph G?
(b) Which vertex has the highest in-degree? Which vertex has the lowest in-degree? Which ver-
tices have the same in-degree and out-degree?
(c) What are the paths from vertex B to F , assuming no vertex is visited twice? Which one is the
shortest path?
(d) Which of the following are cycles in G?
i. (B,C),(C,D),(D,B)
ii. (F,G),(G,F)
iii. (A,B),(B,C),(C,D),(D,B)
CS 70, Fall 2021, HW 3 1
iv. (B,C),(C,D),(D,H),(H,G),(G,F),(F,E),(E,D),(D,B)
(e) Which of the following are walks in G?
i. (E,G)
ii. (E,G),(G,F)
iii. (F,G),(G,F)
iv. (A,B),(B,C),(C,D),(H,G)
v. (E,G),(G,F),(F,G),(G,C)
vi. (E,D),(D,B),(B,E),(E,D),(D,H),(H,G),(G,F)
(f) Which of the following are tours in G?
i. (E,G)
ii. (E,G),(G,F)
iii. (F,G),(G,F)
iv. (E,D),(D,B),(B,E),(E,D),(D,H),(H,G),(G,F)
v. (B,C),(C,D),(D,H),(H,G),(G,F),(F,E),(E,D),(D,B)
In the following three parts, let’s consider a general undirected graph G with n vertices
(n≥ 3). If true, provide a short proof. If false, show a counterexample.
(g) True/False: If each vertex of G has degree at most 1, then G does not have a cycle.
(h) True/False: If each vertex of G has degree at least 2, then G has a cycle.
(i) True/False: If each vertex of G has degree at most 2, then G is not connected.
2 Bipartite Graphs
An undirected graph is bipartite if its vertices can be partitioned into two disjoint sets L, R such
that each edge connects a vertex in L to a vertex in R (so there does not exist an edge that connects
two vertices in L or two vertices in R).
(a) Suppose that a graph G is bipartite, with L and R being a bipartite partition of the vertices.
Prove that ∑
v∈L
deg(v) = ∑
v∈R
deg(v).
(b) Suppose that a graph G is bipartite, with L and R being a bipartite partition of the vertices. Let
s and t denote the average degree of vertices in L and R respectively. Prove that s/t = |R|/|L|.
(c) Prove that a graph is bipartite if and only if it can be 2-colored. (A graph can be 2-colored
if every vertex can be assigned one of two colors such that no two adjacent vertices have the
same color).
CS 70, Fall 2021, HW 3 2
3 Touring Hypercube
In the lecture, you have seen that if G is a hypercube of dimension n, then
• The vertices of G are the binary strings of length n.
• u and v are connected by an edge if they differ in exactly one bit location.
A Hamiltonian tour of a graph is a sequence of vertices v0,v1, . . . ,vk such that:
• Each vertex appears exactly once in the sequence.
• Each pair of consecutive vertices is connected by an edge.
• v0 and vk are connected by an edge.
(a) Show that a hypercube has an Eulerian tour if and only if n is even. (Hint: Euler’s theorem)
(b) Show that every hypercube has a Hamiltonian tour.
4 Tournament
A tournament is defined to be a directed graph such that for every pair of distinct nodes v and w,
exactly one of (v,w) and (w,v) is an edge (representing which player beat the other in a round-robin
tournament). Prove that every tournament has a Hamiltonian path. In other words, you can always
arrange the players in a line so that each player beats the next player in the line.
5 Planarity and Graph Complements
Let G = (V,E) be an undirected graph. We define the complement of G as G = (V,E) where
E = {(i, j)|i, j ∈V, i 6= j}−E; that is, G has the same set of vertices as G, but an edge e exists is G
if and only if it does not exist in G.
(a) Suppose G has v vertices and e edges. How many edges does G have?
(b) Prove that for any graph with at least 13 vertices, G being planar implies that G is non-planar.
(c) Now consider the converse of the previous part, i.e., for any graph G with at least 13 vertices,
if G is non-planar, then G is planar. Construct a counterexample to show that the converse does
not hold.
Hint: Recall that if a graph contains a copy of K5, then it is non-planar. Can this fact be used
to construct a counterexample?
CS 70, Fall 2021, HW 3 3
6 Build-Up Error?
What is wrong with the following “proof”? In addition to finding a counterexample, you should
explain what is fundamentally wrong with this approach, and why it demonstrates the danger
build-up error.
False Claim: If every vertex in an undirected graph has degree at least 1, then the graph is con-
nected.
Proof: We use induction on the number of vertices n≥ 1.
Base case: There is only one graph with a single vertex and it has degree 0. Therefore, the base
case is vacuously true, since the if-part is false.
Inductive hypothesis: Assume the claim is true for some n≥ 1.
Inductive step: We prove the claim is also true for n+1. Consider an undirected graph on n vertices
in which every vertex has degree at least 1. By the inductive hypothesis, this graph is connected.
Now add one more vertex x to obtain a graph on (n+1) vertices, as shown below.
All that remains is to check that there is a path from x to every other vertex z. Since x has degree
at least 1, there is an edge from x to some other vertex; call it y. Thus, we can obtain a path from x
to z by adjoining the edge {x,y} to the path from y to z. This proves the claim for n+1.
7 Graph Coloring
Prove that a graph with maximum degree at most k is (k+1)-colorable. (Hint: consider inducting
over the number of vertices.)
8 Edge Colorings
An edge coloring of a graph is an assignment of colors to edges in a graph where any two edges
incident to the same vertex have different colors. An example is shown on the left.
CS 70, Fall 2021, HW 3 4
(a) Show that the 4 vertex complete graph above can be 3 edge colored. (Use the numbers 1,2,3
for colors. A figure is shown on the right.)
(b) Prove that any graph with maximum degree d ≥ 1 can be edge colored with 2d−1 colors.
(c) Show that a tree can be edge colored with d colors where d is the maximum degree of any
vertex.
CS 70, Fall 2021, HW 3 5
Graph Basics
Bipartite Graphs
Touring Hypercube
Planarity and Graph Complements
Build-Up Error?
Graph Coloring
Edge Colorings