CS 70 Discrete Mathematics and Probability Theory Fall 2021
1 Short Answers
(a) A connected planar simple graph has 5 more edges than it has vertices. How many faces does it have? (b) How many edges need to be removed from a 3-dimensional hypercube to get a tree?
2 Always, Sometimes, or Never
In each part below, you are given some information about the so-called original graph, OG. Using only the information in the current part, say whether OG will always be planar, always be non-planar, or could be either. If you think it is always planar or always non-planar, prove it. If you think it could be either, give a planar example and a non-planar example.
(a) OG can be vertex-colored with 4 colors.
(b) OG requires 7 colors to be vertex-colored.
(c) e ≤ 3v−6, where e is the number of edges of OG and v is the number of vertices of OG. (d) OG is connected, and each vertex in OG has degree at most 2.
(e) Each vertex in OG has degree at most 2.
CS 70, Fall 2021, DIS 3A 1
Trees and Components
Bob removed a degree 3 node from an n-vertex tree. How many connected components are there in the resulting graph? Please provide an explanation.
Given an n-vertex tree, Bob added 10 edges to it and then Alice removed 5 edges. If the resulting graph has 3 connected components, how many edges must be removed in order to remove all cycles from the resulting graph? Please provide an explanation.
4 Hypercubes
The vertex set of the n-dimensional hypercube G = (V, E ) is given by V = {0, 1}n (recall that {0, 1}n denotes the set of all n-bit strings). There is an edge between two vertices x and y if and only if x and y differ in exactly one bit position. These problems will help you understand hypercubes.
(a) Draw 1-, 2-, and 3-dimensional hypercubes and label the vertices using the corresponding bit strings.
(b) Show that for any n ≥ 1, the n-dimensional hypercube is bipartite.
CS 70, Fall 2021, DIS 3A 2