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 H n 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 H 2 looks like this 10 11 00 01 and H 3 looks like this page 3 of 3 110 010 111 011 100 000 a b c d e f g h 101 001 What is Vn What is En Justify your answer Does H17 have an Eulerian cycle Justify your answer Does H 42 have an Eulerian cycle Justify your answer Find a Hamiltonian cycle in H 2 Find a Hamiltonian cycle in H 3 Find a Hamiltonian cycle in H 4 True or false n 2 H n has a Hamiltonian cycle Justify your answer