! ! !CSE 2321 – Foundations I – Autumn, 2015 – Prof. Supowit Homework 4 – Due: Friday, September 25 1. A path in a graph is called simple if all of its vertices are distinct. In the graph depicted below, how many simple paths are there from v to w? Justify your answer. 2. Answer true or false, with justification: (a) If an undirected graph has exactly two vertices of odd degree then there must be a path between those two vertices. (b) If an undirected graph G has exactly three vertices of odd degree then G must have an Eulerian circuit. (c) If a connected, undirected graph has two longest simple paths, P and Q, then P and Q must share a vertex. 3. Let G = (V, E) be an undirected graph in which the degree of each vertex is a multiple of 10 or of 15. Show that |E| is a multiple of 5.! ! !4. Does the following graph have a Hamiltonian circuit? Prove your answer. 5. Either prove or give a counterexample to the following claim: ∀n ≥1( )i i +1( )i=1n∑=n n +1( )n + 2(