## MAT282 Introduction to Discrete Mathematics Midterm Exam 2, Wed 29 November, 8-11 a.m.

1. Give examples of graphs that contain:
1. neither an Eulerian tour (circuit) nor a Hamiltonian cycle;
2. an Eulerian tour but no Hamiltonian cycle;
3. a Hamiltonian cycle but no Eulerian tour;
4. both an Eulerian tour and a Hamiltonian cycle.

2. Given a graph , define the average degree of its vertices as

Prove that for all planar graphs it is the case that , and that for trees the average degree approaches the limit value , as the number of vertices grows.

3. A hypercube graph has as vertices all the -bit binary sequences , and vertices and are connected by an edge if and only if the corresponding binary sequences differ in exactly one position. Determine the chromatic number for each . (Justify your answer.)

4. Design some six-bit, single-error correcting linear code with 8 codewords. Write down the parity-check matrix and the set of codewords of your code. Show how you would use the given parity-check matrix to correct some word containing a single-bit error.

Grading: Problems 1 and 2 each 8 points, Problems 3 and 4 each 7 points, total 30 points.