MPCS 50103 — Problem Set 9

Instructions

This problem set is due on Wednesday March 11, 2020 at 17:00. Solutions to Problems should be submitted on Gradescope and will be graded. 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. Let $G = (V,E)$ be a graph. We define the relation $\sim_G$ on vertices $u,v \in V$ by $u \sim_G v$ if
    1. Show that $\sim_G$ is an equivalence relation.
    2. What do the equivalence classes for $\sim_G$ correspond to?
  2. Let $G = (V,E)$ 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!).
  3. Let $r$ be a fixed vertex in a tree $T = (V,E)$. For every vertex $v \in V$, let $d(v)$ be the length of the path from $r$ to $v$ in $T$. Show that for every edge $(u,v) \in E$, $d(u) \neq d(v)$.
  4. Give an example of each of the following, with a brief justification to aid the grader.
    1. A graph that contains an Eulerian tour but not a Hamiltonian cycle.
    2. A graph that contains a Hamiltonian cycle but not an Eulerian tour.

Exercises

  1. Rosen 10.4 Exercises 19, 35 ($v$ is pendant if $\deg(v) = 1$), 43, 45, 51, 59
  2. Rosen 10.5 Exercises 9, 47, 55, 65
  3. Rosen 11.4 Exercises 1, 7, 11

Reflection

This is the final problem set and the final reflection. This is meant to give you an opportunity to reflect back on your learning in the course. As usual, I will be reading and responding to your submissions.

Completion of this part is optional but is worth an extra 10 marks in total and will be loosely graded on completion/thoughtfulness and not "correctness" (i.e. what you think I want you to say); you should aim for about a paragraph or two of "thoughtfulness".

  1. Did anything go wrong for you in the course? What things went right? Did anything surprise you? If you had to take this course again, would you change anything in how you approached it?
  2. What would you say are the big ideas of this course? How would you explain it to someone who hasn't taken it or is thinking about taking it?
  3. What are your takeaways from this course? Have you gotten what you wanted out of this course?
  4. Is there anything else you'd like to conclude with?