\documentclass[12pt]{amsart}
\pagestyle{empty}
\usepackage[hmargin=1in,vmargin=1in]{geometry}
\usepackage{url,  mathrsfs}
\usepackage{hyperref}
\usepackage{fancyhdr} 
\usepackage[T1]{fontenc}


\usepackage{url,  mathrsfs}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{graphicx,  epstopdf}
\usepackage{subfig}
\usepackage{color}
\usepackage{bbm}
\usepackage{subfloat}
\usepackage[draft]{fixme}
\usepackage{bm} 
\usepackage{bbm} 
\usepackage{epigraph}
\usepackage{endnotes}
\usepackage{ifpdf}
\usepackage{array}

\usepackage{multicol}
\usepackage{multirow}
\usepackage{graphicx}
\usepackage{tikz}
\usetikzlibrary{decorations.markings,arrows}
\usetikzlibrary{shapes.geometric}

\newcommand{\A}{\mathbb{A}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\C}{\mathbb{C}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\V}{\mathcal{V}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\ol}{\overline}
\newcommand{\J}{\mathcal{J}}
\newcommand{\X}{\mathcal{X}}
\theoremstyle{definition}
\newtheorem{prob}{Problem}
\newtheorem{extraProb}{Extra Problem}

\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\cone}{cone}
\DeclareMathOperator{\ext}{ext}




\begin{document}
 \thispagestyle{empty}
\begin{center} {\large \textbf{Math 409 -- Homework  8}} \smallskip \\ 
Due on Friday, May 31\ \\ \ \\
 \end{center}

You are welcome to talk with other students in the class about problems but should write up solutions on your own. 
Solutions can be handwritten or typed but need to be legible and submitted via Gradescope by the end of the day 
on Friday. You should justify all your answers in order to receive full credit.   Late submissions can be turned in until the end of Sunday (see the syllabus for late policy). 


\bigskip 

\begin{prob}
Let $M$ be a \emph{maximal} matching in $G = (V,E)$, meaning that for every $e\in E\backslash M$, $M\cup\{e\}$ is not a matching in $G$, and let $M^*$ be a matching in $G$ of maximum size. \smallskip 
\begin{itemize}
\item[(a)] Show that every $\{u,v\} \in M^*$, at least one of $u$ and $v$ are matched in $M$ (possibly to a different vertex).  \smallskip 
\item[(b)] Show that $|M^*|/2 \leq |M| \leq |M^*|$
\end{itemize}
This means that we can get a matching $M$ that's within a factor of 2 of being maximum by greedily adding edges to $M$ until we can't add any more. 
\end{prob}

\bigskip 
\begin{prob}
  Let $G = (V,E)$ be an undirected graph. For $U \subseteq V$, let $\textrm{odd}(U)$ be the number of
  connected components in $G \setminus U$ that have an odd number of vertices.
  Below is a schematic picture where $C_1, \hdots, C_{{\rm odd}(U)}$ and $\tilde{C}_1, \hdots, \tilde{C}_{{\rm even}(U)}$ are the connected components of $G\backslash U$ with an odd and even number of vertices, respectively. \smallskip 
   \begin{center}
\begin{tikzpicture}
\node[ellipse,draw, fill=gray!20] (o1) at (0, 2) {$ \ \ C_1 \ \ $}; 
\node[ellipse,draw, fill=gray!20] (o2) at (2, 2) {$ \ \ C_2 \ \ $}; 
\node (o3) at (4,2) {$\hdots$}; 
\node[ellipse,draw, fill=gray!20] (o4) at (6, 2) {$C_{{\rm odd}(U)}$}; 
\node[ellipse,draw, fill=gray!20] (u) at (3, 1) {$ \ \ \ \ \ \ \ U \ \ \ \ \ \ \ $}; 
\node[ellipse,draw, fill=gray!20] (e1) at (0, 0) {$ \ \ \tilde{C}_1 \ \ $}; 
\node[ellipse,draw, fill=gray!20] (e2) at (2, 0) {$ \ \ \tilde{C}_2 \ \ $}; 
\node (e3) at (4,0) {$\hdots$}; 
\node[ellipse,draw, fill=gray!20] (e4) at (6, 0) {$\tilde{C}_{{\rm even}(U)}$};
\draw (o1) -- (u) -- (o2);
\draw (o3) -- (u) -- (o4);
\draw (e1) -- (u) -- (e2);
\draw (e3) -- (u) -- (e4);
\end{tikzpicture}
\end{center}


  \begin{enumerate}
  \item[(a)] In the example graph below, find a set $U$ of vertices so that $\textrm{odd}(U) > |U|$. \smallskip 
    \begin{center}
\begin{tikzpicture}
\node[circle,fill=black,inner sep=2pt, label=above:$v_1$] (v1) at (0, 0) {}; 
\node[circle,fill=black,inner sep=2pt, label=above:$v_2$] (v2) at (-1,0.5) {}; 
\node[circle,fill=black,inner sep=2pt, label=below:$v_3$] (v3) at (-1,-0.5) {}; 
\node[circle,fill=black,inner sep=2pt] (v4) at (1,0) {}; 
\node (v4n) at (.7,.2) {$v_4$};
\node[circle,fill=black,inner sep=2pt, label=below:$v_5$] (v5) at (2,-0.5) {}; 
\node[circle,fill=black,inner sep=2pt, label=below:$v_6$] (v6) at (3,-0.5) {}; 
\node[circle,fill=black,inner sep=2pt, label=above:$v_7$] (v7) at (3,0.5) {}; 
\node[circle,fill=black,inner sep=2pt, label=above:$v_8$] (v8) at (2,0.5) {};
\node[circle,fill=black,inner sep=2pt, label=below:$v_9$] (v9) at (1,-1) {}; 
\node[circle,fill=black,inner sep=2pt] (v10) at (1,1) {}; 
\node (v10n) at (.7,.8) {$v_{10}$};
\node[circle,fill=black,inner sep=2pt, label=above:$v_{11}$] (v11) at (.2,1.5) {}; 
\node[circle,fill=black,inner sep=2pt, label=above:$v_{12}$] (v12) at (1.8,1.5) {}; 
\draw (v1) -- (v2) -- (v3) -- (v1) -- (v4) -- (v10) -- (v11) -- (v12) -- (v10);
\draw (v4) -- (v8) -- (v7) -- (v6) -- (v5) -- (v4) -- (v9);
\end{tikzpicture}
\end{center}
    \item[(b)] Now consider an arbitrary graph $G = (V,E)$. Prove that if there is a set $U \subseteq V$ with $\textrm{odd}(U) > |U|$, then $G$ does not contain a perfect matching.
    \end{enumerate}

\end{prob}

\bigskip 

\vfill 

\emph{Problem 3 on the next page. }
\pagebreak 


\begin{prob}
  Let $G = (V,E)$ be a directed graph with non-negative edge cost $c : E \to \R_{\geq 0}$ and
  let $s,t \in V$ be two distinguished nodes. 
  Edges are labelled with one of three colors, red, blue and green. A \emph{red-green-blue walk} is a sequence of edges $e_1,\ldots,e_k \in E$  so that the colors of the visited edges are red-green-blue-red-green-blue, etc. (More formally $e_{3j+1}$ is red,  $e_{3j+2}$ is green, and $e_{3j+3}$ is blue for every $j$). The cost of such a walk is $\sum_{i=1}^k c(e_i)$. \smallskip 
  \begin{enumerate}
  \item[(a)] What is the minimum cost red-green-blue walk from $s$ to $t$ in the depicted instance?  Each edge $e$ is labeled with its cost $c(e)$.
    \begin{center}
\begin{center}
\begin{tikzpicture}[
    decoration={markings,mark=at position 0.6 with {\arrow{triangle 60}}}, scale=1
    ]
\node[circle,draw] (s) at (0, 0) {$s$}; 
\node[circle,draw] (a) at (1,1.5) {$a$}; 
\node[circle,draw] (b) at (3,-1.5) {$b$}; 
\node[circle,draw] (c) at (3,0) {$c$}; 
\node[circle,draw] (d) at (3,1.5) {$d$}; 
\node[circle,draw] (e) at (5,-1.5) {$e$}; 
\node[circle,draw] (t) at (6,0) {$t$}; 
\draw[red,postaction={decorate}] (s) -- node[above]{$2$} (a);
\draw[green!50!black, postaction={decorate}] (a) -- node[above]{$1$} (d);
\draw[red,postaction={decorate}] (c) -- node[above]{$10$} (s);
\draw[blue,postaction={decorate}] (d) -- node[left]{$1$} (c);
\draw[green!50!black,postaction={decorate}] (d) -- node[above]{$1$} (t);
\draw[green!50!black,postaction={decorate}] (s) -- node[above]{$3$} (b);
\draw[green!50!black,postaction={decorate}] (c) -- node[above]{$0$} (t);
\draw[blue,postaction={decorate}] (b) -- node[above]{$1$} (e);
\draw[red,postaction={decorate}] (e) -- node[above]{$1$} (t);
\end{tikzpicture}
\end{center}
{\color{red}Red edges: $\{sa, cs, et\}$}, {\color{green!50!black}Green edges: $\{sb, ad, ct, dt\}$},   {\color{blue}Blue edges: $\{be, dc\}$}
    \end{center}
    \emph{Hint:} The cost should be 19.\smallskip 
  \item[(b)] Design a polynomial time algorithm for finding the minimum cost red-green-blue walk from $s$ to $t$ in a general graph $G = (V,E)$. Explain the running time bound that you get. Argue why the algorithm is correct. \\
 \emph{Hint:}  Reread the algorithm to find $M$-alternating walks in Section 8. 
  \end{enumerate}
\end{prob}

\end{document}