\documentclass{article}
\usepackage{amssymb}
\usepackage{multicol}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{verbatim}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsmath, epsfig}
\setlength{\parskip}{8pt}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
%\theoremstyle{Remark}
%\newtheorem{remark}
\renewcommand{\today}{}
\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\Lap}[1]{\mathcal{L}\left\{#1\right\}}


\addtolength{\topmargin}{-.875in}
\addtolength{\textheight}{1.75in}

\newcommand{\solution}[1]{
\color{red}\begin{quote}Solution:\quad 
\color{black} #1
\end{quote}\color{black}
}
\newcommand{\ba}{\backslash}
\newcommand{\Ber}{\hbox{Ber}}
\newcommand{\p}[1]{\mathbb{P}\left(#1\right)}
\newcommand{\e}[1]{\mathbb{E}(#1)}
\newcommand{\Po}[1]{\hbox{Po}(#1)}
\newcommand{\var}[1]{\hbox{Var}(#1)}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\C}{\mathbb{C}}
\DeclareMathOperator{\Diam}{diam}
\newcommand{\diam}[1]{\Diam\left(#1\right)}


\begin{document}
\title{Math 301 Homework}
\author{Mary Radcliffe}
\date{Bonus to Posets: problem 5}
\maketitle

The problem in your homework asks you to prove that Hall's Theorem, Dilworth's Theorem, and K\"{o}nig's Theorem are equivalent. For 10 points each, you may add one or both of the following equivalences to the problem:

\begin{itemize}
\item Menger's Theorem. A graph $G$ is called $k$-connected if there does not exist a set $S$ of $k-1$ vertices such that $G\ba S$ is disconnected. That is to say, if you wish to disconnect the graph, you must remove at least $k$ vertices to do so.

Given $u$ and $v$ vertices of $G$, we say two paths from $u$ to $v$ are internally disjoint if those two paths share no vertices other than the endpoints $u$ and $v$. A set of paths is called internally disjoint if the paths in the set are pairwise internally disjoint.

Menger's Theorem states the following:
\begin{quote}
A graph $G$ is $k$-connected if and only if for every $u, v\in V(G)$, there exist at least $k$ internally disjoint paths between $u$ and $v$.
\end{quote}

\item Max-Flow/Min-Cut Theorem. Let $G$ be a directed graph, with a source $s$ and a sink $t$. (Note: A source is a vertex from which all incident edges direct, and a sink is a vertex to which all incident edges direct). We shall write $uv$ to denote an edge from $u$ toward $v$, and $vu$ for the opposite direction. Weight each edge $uv$ with positive weight $w_{uv}$. A flow on $G$ is an assignment $f_{uv}$ to each edge $uv$ such that the following two conditions hold:
\begin{enumerate}
\item $f_{uv}\leq w_{uv}$ for all $uv$
\item For all $v\in V(G)$ other than $s$, $t$, $\sum_{uv\in E} f_{uv} = \sum_{vu\in E} f_{vu}$, and $\sum_{su\in E} f_{su} =\sum_{ut\in E} f_{ut}$
\end{enumerate}
That is, the flow in to a vertex is equal to the flow out, and the flow is bounded on each edge by its weight (sometimes called capacity), and all flow originates at $s$ and ends at $t$.

A maximum flow from $s$ to $t$ is a flow for which $\sum_{su\in E}f_{su}$ is maximized, and this maximum value is called the weight of the flow.

A cut in $G$ is a set of edges $S$ such that $G\ba S$ is disconnected. The weight of a cut $S$ is $\sum_{e\in S} w_e$. A minimum cut is one for which the weight of the cut is minimum among all cuts.

The Max Flow/Min Cut Theorem states the following:
\begin{quote}
For any directed graph with source and sink as described above, the weight of the maximum flow from $s$ to $t$ is equal to the weight of the minimum cut in $G$. 
\end{quote}
\end{itemize}


\end{document}