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 n n 1 n 2 n 1 i i 1 3 i 1
View Full Document
Unlocking...