Description

CS 70 Discrete Mathematics and Probability Theory

1 Cube Dual
We define a graph G by letting the vertices be the corners of a cube and having edges connecting adjacent corners. Define the dual of a planar graph G to be a graph G0, constructed by replacing each face in G with a vertex, and an edge between every vertex in G0 if the respective faces are adjacent in G.
(a) Draw a planar representation of G and the corresponding dual graph. Is the dual graph planar? (Hint: think about the act of drawing the dual)
(b) Is G0 bipartite?
2 True or False
(a) Any pair of vertices in a tree are connected by exactly one path.
(b) Adding an edge between two vertices of a tree creates a new cycle.
(c) Adding an edge in a connected graph creates exactly one new cycle.
3 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.

(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.