CMSC 27100 — Problem Set 9

Instructions

This problem set is due on Wednesday December 4, 2019 at 23:59. Late submissions will be accepted without penalty until Friday December 6, 2019 at 23:59. Solutions to Problems should be submitted on Gradescope and will be graded. Solutions to Extra Credit Problems will be graded and the grade will be added to the grade of this problem set. Solutions to Exercises will not be graded and you should not submit them, although we will be happy to discuss them with you.

Problems

  1. Consider the following graphs $F, G, H$, in order from left to right. For each pair of graphs $(F,G)$, $(G,H)$, and $(F,H)$, determine with justification which pairs of graphs are isomorphic and which pairs are not.
  2. Let $G$ be a $k$-regular bipartite graph.
    1. Prove that if $(V_1,V_2)$ is a bipartition of $G$, then $|V_1| = |V_2|$.
    2. Show that $G$ has a complete matching.
  3. Let $G$ be a graph with two vertices $u$ and $v$ of odd degree and all other vertices have even degree. Show that $u$ and $v$ are in the same component of $G$ (this means $G$ is not necessarily connected!).
  4. Let $G = (V,E)$ be a graph such that all vertices have degree $\leq d$. Show that $G$ is $(d+1)$-colourable.

Extra Credit Problems

  1. Solve the recurrence $a_n = 4 a_{n-1} - a_{n-2} - 6 a_{n-3}$ under the initial conditions $a_0 = 1, a_1 = 0, a_2 = 6$.
  2. Solve the recurrence $a_n = - a_{n-1} + 16 a_{n-2} - 20 a_{n-3}$ under the initial conditions $a_0 = 1, a_1 = -17, a_2 = 75$.

Exercises

  1. Show that for any graph $G = (V,E)$, $|E| \leq \binom{|V|}{2}$.
    1. For any graph $G = (V,E)$, with $|V| = n$, show that $G$ is a spanning subgraph of $K_n$.
    2. Consider $K_n = (V_n,E_n)$. Show that for any subset $V_m \subseteq V_n$ with $|V_m| = m$, the subgraph induced by $V_m$ is (isomorphic to) $K_m$.
  3. Rosen 10.2 Exercises 5, 55, 59
  4. Rosen 10.3 Exercises 9, 29, 45, 49
  5. Rosen 10.4 Exercises 19, 29, 43, 45, 59
  6. Rosen 8.1 Exercises 7, 9
  7. Rosen 8.2 Exercises 3, 15, 17, 19