! ! page!1!of!3!CSE 2321 – Foundations I – Autumn, 2015 – Prof. Supowit Homework 3 – Due: Friday, Sept. 16 1. Let 1, 2, …, n be distinct lines in the Euclidean plane, and let A be the set of points formed by intersections of these lines. Characterize A using set notation and quantifiers. 2. Express (as simply as you can) each of the following sentences without the use of universal quantification: (a) ∀x( )∃y( )∀z( )P(x, y, z)[ ] (b) ∃y( )∀x( )P x, y( )⇒ ∀x( )Q x, y( )$%&' 3. Express (as simply as you can) each of the sentences in problem (2) without the use of existential quantification. 4. A sequence of natural numbers a1, a2, …, an( )is said to be a degree sequence if there exists an undirected graph on vertices v1, v2, …, vn{ }such that degree vi( )= ai for each i = 1, 2, …, n. (a) Is (0, 1, 1, 1, 2, 2, 3, 4) a degree sequence? Prove your answer. (b) Is (0, 1, 1, 1, 2, 3, 3, 4) a degree sequence? Prove your answer. (c) FOR EXTRA FUN: try to devise an algorithm for determining whether a given sequence of numbers is a degree sequence. 5. The “pigeonhole principle” states that if n +1 objects (e.g., pigeons) are to be distributed into n holes then some hole must contain at least two objects. This observation is obvious but useful. Employ the pigeonhole principle to prove the following: Claim: Let G be an undirected graph with at least two vertices. Then there exist distinct vertices v and w in G that have the same degree.! ! page!2!of!3!6. The Hamming cube of dimension n is defined as the undirected graph Hn= Vn, En( )with vertices Vn = { w : w is a binary string of length n } and En = { {v, w} : v and w differ in exactly one component}. For example, H2 looks like this and H3 looks like this 10110100! ! page!3!of!3! (a) What is Vn? (b) What is En? Justify your answer. (c) Does H17 have an Eulerian cycle? Justify your answer. (d) Does H42 have an Eulerian cycle? Justify your answer. (e) Find a Hamiltonian cycle in H2. (f) Find a Hamiltonian cycle in H3. (g) Find a Hamiltonian cycle in H4. (h) True or false: ∀n ≥ 2( )Hn has a Hamiltonian cycle[ ]. Justify your answer.