# Math 55 RRR Week Problems --- Solutions

1. Suppose $G=(V,E)$ and $H=(V,F)$ with $G=H+e$ where $e=\{x,y\}\notin F$. We will show that $\chi(G)\le \chi(H)+1$. Let $f:V\rightarrow \{1,\ldots,\chi(H)\}$ be a coloring of $H$. If $f$ is a valid coloring of $G$ then $\chi(G)=\chi(H)$. Otherwise, we must have $f(x)=f(y)$ since every other edge of $G$ belongs to $H$ and and has endpoints of different colors. Let $f':V\rightarrow\{1\ldots,\chi(H)+1\}$ be defined by $f'(z)=f(z)$ for all $z\neq x$, and $f'(x)=\chi(H)+1$. Then we have $f'(x)\neq f'(y)$ and $f'$ is a valid coloring of $G$, so $\chi(G)=\chi(H)+1$. Thus, we have shown that $\chi(H)$ is either $\chi(G)$ or $\chi(G)-1$, as desired.

2. Let $x$ and $y$ be the two vertices of odd degree in $G$. Suppose there is no path from $x$ to $y$ in $G$. Then there must be two connected components $H_1$ and $H_2$ of $G$ such that $x\in H_1$, $y\in H_2$, and all other vertices of $H_1$ and $H_2$ have even degree (since the degree of every vertex in $H_1$ or $H_2$ is equal to its degree in $G$). But now $H_1$ has an odd number of vertices (one) with odd degree, which violates the handshaking lemma, a contradiction.

3. Suppose $\pi_1$ and $\pi_2$ are two paths of maximum length in $G$. Let this length be $k$. Assume for contradiction that these paths do not share a common vertex. Let
$$ t = \min\{dist(x,y):x\in \pi_1, y\in \pi_2\}$$
be the minimum distance between a vertex in $\pi_1$ and a vertex in $\pi_2$ and note that $t\ge 1$. Suppose this distance is achieved by vertices $x\in \pi_1$ and $y\in\pi_2$ (i.e., $dist(x,y)=t$) and call the shortest path connecting $x$ and $y$ in $G$ $\gamma$. Notice that $\gamma$ does not intersect $\pi_1$ or $\pi_2$ except possibly at its endpoints; if it did, then a strict subpath of $\gamma$ would connect endpoints in $\pi_1$ and $\pi_2$, contradicting our choice of $\gamma$.
$$ $$
Let $s_1,t_1$ be the endpoints of $\pi_1$ and let $s_2,t_2$ be the endpoints of $\pi_2$. Consider the two subpaths of $\pi$ from $s_1$ to $x$ and from $t_1$ to $x$ and notice that one of these must have length greater than or equal to $k/2$, since the sum of the lengths is $k$; call this subpath $\pi_1'$. Similarly, choose a subpath $\pi_2'$ of $\pi_2$ with initial vertex $y$ of length at least $k/2$. Now consider the concatenated path
$$P=\pi_1',\gamma,\pi_2'$$
and notice that the length of $P$ is at least $k/2+k/2+t>k$. This violates the maximality of $\pi_1$ and $\pi_2$, a contradiction.

4. See the posted solutions.