# Math 55 RRR Week Problems

1. Show that if $G$ is a simple graph and $H$ is obtained by deleting one edge from $G$, then either $\chi(H)=\chi(G)$ or $\chi(H)=\chi(G)-1$ (where $\chi$ denotes the chromatic number).
2. Show that if $G$ has exactly two vertices of odd degree, then there must be a path from one to the other.
3. Show that if $\pi_1$ and $\pi_2$ are two simple paths of maximum length (over all simple paths) in a simple graph $G$, then they must have a common vertex.
4. Practice Final1 number 10.