Description

CS 70 Discrete Mathematics and Probability Theory

1 Eulerian Tour and Eulerian Walk

(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.
2 Banquet Arrangement
In the words of the great Ana Lynch, “Let’s have a kiki.”
Suppose n people are attending a kiki, and each of them has at least m friends (2 ≤ m ≤ n), where friendship is mutual. Prove that we can put at least m+1 of the attendants on the same round table, so that each person sits next to his or her friends on both sides.
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 degv = 2|E|.
(ii) Induction on m = |E| (number of edges)
(iii) Induction on n = |V| (number of vertices)