Midterm Exam 2, Wed 29 November, 8-11 a.m.

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

- 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. - 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.) - 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.