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 $G = (V,E)$, define the average degree of its vertices as
   
   $$\bar{\delta}_G = \frac{1}{\vert V\vert}\sum_{u \in V} \deg(u).$$
   
   
   Prove that for all planar graphs $G$ it is the case that $\bar{\delta}_G < 6$, and that for trees $T$ the average degree approaches the limit value $\lim \bar{\delta}_T = 2$, as the number of vertices grows.

3. A hypercube graph $H_n$ has as vertices all the $n$-bit binary sequences $u \in \{0,1\}^n$, and vertices $u$ and $v$ are connected by an edge if and only if the corresponding binary sequences differ in exactly one position. Determine the chromatic number $\chi(H_n)$ for each $n$. (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.