Description
1 Short Answer: Graphs
(a) Bob removed a degree 3 node in an n-vertex tree, how many connected components are in the
resulting graph? (An expression that may contain n.)
(b) Given an n-vertex tree, Bob added 10 edges to it, then Alice removed 5 edges and the resulting
graph has 3 connected components. How many edges must be removed to remove all cycles
in the resulting graph? (An expression that may contain n.)
(c) True or False: For all n 3, the complete graph on n vertices, Kn has more edges than the
n-dimensional hypercube. Justify your answer.
(d) A complete graph with n vertices where n is an odd prime can have all its edges covered with
x Hamiltonian cycles (a Hamiltonian cycle is a cycle where each vertex appears exactly once).
What is the number, x, of such cycles required to cover the a complete graph? (Answer should
be an expression that depends on n.)
(e) Give a set of edge-disjoint Hamiltonian cycles that covers the edges of K5, the complete graph
on 5 vertices. (Each path should be a sequence (or list) of edges in K5, where an edge is written
as a pair of vertices from the set {0,1,2,3,4} – e.g: (0,1),(1,2).)
CS 70, Fall 2018, HW 3 1
2 Eulerian Tour and Eulerian Walk
(a) Is there an Eulerian tour in the graph above?
(b) Is there an Eulerian walk in the graph above?
(c) What is the condition that there is an Eulerian walk in an undirected graph? Briefly justfy your
answer.
3 Bipartite Graph
A bipartite graph consists of 2 disjoint sets of vertices (say L and R), such that no 2 vertices
in the same set have an edge between them. For example, here is a bipartite graph (with L =
{green vertices} and R = {red vertices}), and a non-bipartite graph.
Figure 1: A bipartite graph (left) and a non-bipartite graph (right).
Prove that a graph is bipartite if and only if it has no tours of odd length.
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: the vertices can be partitioned into two groups so that every edge goes between the two groups.
CS 70, Fall 2018, HW 3 2
5 Triangulated Planar Graph
In this problem you will prove that every triangulated planar graph (every face has 3 sides; that is,
every face has three edges bordering it, including the unbounded face) contains either (1) a vertex
of degree 1, 2, 3, 4, (2) two degree 5 vertices which are adjacent, or (3) a degree 5 and a degree 6
vertices which are adjacent. Justify your answers.
(a) Place a “charge” on each vertex v of value 6 degree(v). What is the sum of the charges on
all the vertices? (Hint: Use Euler’s formula and the fact that the planar graph is triangulated.)
(b) What is the charge of a degree 5 vertex and of a degree 6 vertex?
(c) Suppose now that we shift 1/5 of the charge of a degree 5 vertex to each of its neighbors that
has a negative charge. (We refer to this as “discharging” the degree 5 vertex.) Conclude the
proof under the assumption that, after discharging all degree 5 vertices, there is a degree 5
vertex with positive remaining charge.
(d) If no degree 5 vertices have positive charge after discharging the degree 5 vertices, does there
exist any vertex with positive charge after discharging? If there is such a vertex, what are the
possible degrees of that vertex?
(e) Suppose there exists a degree 7 vertex with positive charge after discharging the degree 5
vertices. How many neighbors of degree 5 might it have?
(f) Continuing from Part (e). Since the graph is triangulated, are two of these degree 5 vertices
adjacent?
(g) Finish the proof from the facts you obtained from the previous parts.
CS 70, Fall 2018, HW 3 3
