\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{enumitem}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage[table]{xcolor}
\usepackage[all,arc]{xy}
\usepackage{color, colortbl}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.15in}
\setlength{\evensidemargin}{.15in}
\setlength{\textwidth}{6.2in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{8.6in}


\input{preamble.tex}

\begin{document}

\homework{9: Algebraic Flows}{Due Friday, Week 5}

Do \textbf{one} of the following \textbf{three} problems!   Have fun!

\begin{enumerate}
\item Show that $\varphi($Pete$) = 5$, by proving that no 4-flow exists on the Petersen graph, while a 5-flow does exist.
\item Let $G$ be a multigraph containing an edge $e = \{x,y\}$, where $x \neq y$.  Let $G / e$ denote the graph formed by ``contracting'' the edge $e$ to a single point.  Finally, let $A$ be any abelian group.

Prove, as claimed in class, that there is a 1-1 correspondence between $A$-flows on $G/e$ and $A$-circulations on $G$ that are nonzero on every edge except for maybe $e$.
\item In class, we claimed that a graph has a $k$-flow if and only if it has a $\mathbb{Z}/k\mathbb{Z}$-flow.  Prove this!
\end{enumerate}
\end{document}






