CS 70 Discrete Mathematics and Probability Theory Fall 2021
1 True or False
(a) Any pair of vertices in a tree are connected by exactly one path.
(b) A simple graph obtained by adding an edge between two vertices of a tree creates a cycle.
(c) Adding an edge in a connected graph creates exactly one new cycle.
2 Eulerian Tour and Eulerian Walk
CS 70, Fall 2021, DIS 2B 1
(a) Is there an Eulerian tour in the graph above? If no, give justification. If yes, provide an example.
(b) Is there an Eulerian walk in the graph above? An Eulerian walk is a walk that uses each edge exactly once. If no, give justification. If yes, provide an example.
(c) What is the condition that there is an Eulerian walk in an undirected graph? Briefly justify your answer.
3 Not everything is normal: Odd-Degree Vertices
Claim: Let G = (V,E) be an undirected graph. The number of vertices of G that have odd degree is even. Prove the claim above using:
(i) Direct proof (e.g., counting the number of edges in G). Hint: in lecture, we proved that ¡Æv¡ÊV deg v = 2|E |.
(ii) Induction on m = |E| (number of edges) (iii) Induction on n = |V | (number of vertices)
CS 70, Fall 2021, DIS 2B 2
4 Coloring Trees
Prove that all trees with at least 2 vertices are bipartite: the vertices can be partitioned into two groups so that every edge goes between the two groups.
[Hint: Use induction on the number of vertices.]
CS 70, Fall 2021, DIS 2B 3