Starting from:
$26.10
Discrete Mathematics and Probability Theory HW 3
CS 70 Discrete Mathematics and Probability Theory
HW 3
Sundry
Before you start your homework, write down your team. Who else did you work with on this
homework? List names and email addresses. (In case of homework party, you can also just describe
the group.) How did you work on this homework? Working in groups of 3-5 will earn credit for
your "Sundry" grade.
Please copy the following statement and sign next to it:
I certify that all solutions are entirely in my words and that I have not looked at another student’s
solutions. I have credited all external sources in this write up.
1 Build-Up Error?
What is wrong with the following "proof"?
False Claim: If every vertex in an undirected graph has degree at least 1, then the graph is connected.
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.
CS 70, Fall 2017, HW 3 1
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.
2 Proofs in Graphs
Please prove or disprove the following claims.
(a) In Old California, all roads were one way streets. Suppose Old California had n cities (n ≥ 2)
such that for every pair of cities X and Y, either X had a road to Y or Y had a road to X. Prove
or disprove that there existed a city which was reachable from every other city by traveling
through at most 2 roads.
[Hint: Induction]
(b) In lecture, we have shown that a connected undirected graph has an Eulerian tour if and only
if every vertex has even degree.
Consider a connected graph G with n vertices which has exactly 2m vertices of odd degree,
where m 0. Prove or disprove that there are m walks that together cover all the edges of G
(i.e., each edge of G occurs in exactly one of the m walks, and each of the walks should not
contain any particular edge more than once).
3 Connectivity
Consider the following claims regarding connectivity:
(a) Prove: If G is a graph with n vertices such that for any two non-adjacent vertices u and v, it
holds that degu+degv ≥ n−1, then G is connected.
[Hint: Show something more specific: for any two non-adjacent vertices u and v, there must
be a vertex w such that u and v are both adjacent to w.]
(b) Give an example to show that if the condition degu + degv ≥ n − 1 is replaced with degu +
degv ≥ n−2, then G is not necessarily connected.
(c) Prove: For a graph G with n vertices, if the degree of each vertex is at least n/2, then G is
connected.
CS 70, Fall 2017, HW 3 2
(d) Prove: If there are exactly two vertices with odd degrees in a graph, then they must be connected to each other (meaning, there is a path connecting these two vertices).
[Hint: Proof by contradiction.]
4 Leaves in a Tree
A leaf in a tree is a vertex with degree 1.
(a) Consider a tree with n ≥ 3 vertices. What is the largest possible number of leaves the tree
could have? Prove that this maximum m is possible to achieve, and further that there cannot
exist a tree with more than m leaves.
(b) Prove that every tree on n ≥ 2 vertices must have at least two leaves.
5 Coloring Trees
(a) What is the minimum number of colors needed to color a tree? Prove your claim.
(b) Prove that all trees are bipartite.
[Hint: How does your answer to part (a) relate to this?]
6 Edge-Disjoint Paths in a Hypercube
Prove that between any two distinct vertices x, y in the n-dimensional hypercube graph, there are
at least n edge-disjoint paths from x to y (i.e., no two paths share an edge, though they may share
vertices).
CS 70, Fall 2017, HW 3 3
HW 3
Sundry
Before you start your homework, write down your team. Who else did you work with on this
homework? List names and email addresses. (In case of homework party, you can also just describe
the group.) How did you work on this homework? Working in groups of 3-5 will earn credit for
your "Sundry" grade.
Please copy the following statement and sign next to it:
I certify that all solutions are entirely in my words and that I have not looked at another student’s
solutions. I have credited all external sources in this write up.
1 Build-Up Error?
What is wrong with the following "proof"?
False Claim: If every vertex in an undirected graph has degree at least 1, then the graph is connected.
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.
CS 70, Fall 2017, HW 3 1
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.
2 Proofs in Graphs
Please prove or disprove the following claims.
(a) In Old California, all roads were one way streets. Suppose Old California had n cities (n ≥ 2)
such that for every pair of cities X and Y, either X had a road to Y or Y had a road to X. Prove
or disprove that there existed a city which was reachable from every other city by traveling
through at most 2 roads.
[Hint: Induction]
(b) In lecture, we have shown that a connected undirected graph has an Eulerian tour if and only
if every vertex has even degree.
Consider a connected graph G with n vertices which has exactly 2m vertices of odd degree,
where m 0. Prove or disprove that there are m walks that together cover all the edges of G
(i.e., each edge of G occurs in exactly one of the m walks, and each of the walks should not
contain any particular edge more than once).
3 Connectivity
Consider the following claims regarding connectivity:
(a) Prove: If G is a graph with n vertices such that for any two non-adjacent vertices u and v, it
holds that degu+degv ≥ n−1, then G is connected.
[Hint: Show something more specific: for any two non-adjacent vertices u and v, there must
be a vertex w such that u and v are both adjacent to w.]
(b) Give an example to show that if the condition degu + degv ≥ n − 1 is replaced with degu +
degv ≥ n−2, then G is not necessarily connected.
(c) Prove: For a graph G with n vertices, if the degree of each vertex is at least n/2, then G is
connected.
CS 70, Fall 2017, HW 3 2
(d) Prove: If there are exactly two vertices with odd degrees in a graph, then they must be connected to each other (meaning, there is a path connecting these two vertices).
[Hint: Proof by contradiction.]
4 Leaves in a Tree
A leaf in a tree is a vertex with degree 1.
(a) Consider a tree with n ≥ 3 vertices. What is the largest possible number of leaves the tree
could have? Prove that this maximum m is possible to achieve, and further that there cannot
exist a tree with more than m leaves.
(b) Prove that every tree on n ≥ 2 vertices must have at least two leaves.
5 Coloring Trees
(a) What is the minimum number of colors needed to color a tree? Prove your claim.
(b) Prove that all trees are bipartite.
[Hint: How does your answer to part (a) relate to this?]
6 Edge-Disjoint Paths in a Hypercube
Prove that between any two distinct vertices x, y in the n-dimensional hypercube graph, there are
at least n edge-disjoint paths from x to y (i.e., no two paths share an edge, though they may share
vertices).
CS 70, Fall 2017, HW 3 3
1 file (199.2KB)
