\documentclass[11pt]{article}
\usepackage{amsmath}  % this adds some math 
\usepackage{fullpage}
\usepackage{tikz}            % if you delete this, you will have trouble with the included picture. You can delete the picture.
\usepackage{chessboard}
\usepackage{hyperref}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amsmath}
\usetikzlibrary{shapes.geometric}
\usetikzlibrary{shapes.multipart}
\usetikzlibrary{arrows}

% If you have a problem, please let me know sooner than later

\newcommand\name{Chuck Norris} %%%%%%%%%%%%%%  WRITE YOUR NAME HERE



\newcounter{excounter}
\setcounter{excounter}{1}
\newcommand\question[2]{\vskip 1em  \noindent\textbf{\arabic{excounter}\addtocounter{excounter}{1}:} \emph{#1} \noindent#2}


% You can also erase this if you do not have package hancyhdr
% Fancy footnote......... 
\usepackage{fancyhdr}  %% If it does not work with your latex installation, you may just delete this...
\pagestyle{fancy}
\usepackage{lastpage}
\rfoot{\name, page \thepage/\pageref{LastPage}}
\cfoot{}
\rhead{}
\lhead{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}



%%% Note that you do not have to use this template. You can use your own writeup or make any adjustment to this one you like.
%%% This is provided only for your convenience. 


\begin{document}


{\bf MATH314  \hspace{1cm} HW 7\hfill \name}
\vskip 1em

% left column
\begin{minipage}[t]{0.75\textwidth}
Due \textbf{Mar 10} before class, \textbf{answer without justification will receive 0 points}.
The typing the HW in \LaTeX{} is optional. 
\end{minipage}
% right box for score column
\begin{minipage}[t]{0.25\textwidth}
\hfill \begin{tabular}{|r|}
\hline
\hskip 3em Score \hskip 3em \\
\hline \\ \\
\hskip 3em /60 \\
\hline
\end{tabular}
\end{minipage}





\question{}{
Let $G$ be a $k$-connected graph and let $S$ be any set of $k$ vertices. Show that if a graph $H$ is obtained from $G$ by adding a new vertex $w$ and joining $w$ to the vertices of $S$, then $H$ is also $k$-connected.
}


\textbf{Solution:}

\question{5.36}{
Let $G$ be a $k$-connected graph of order $n \geq 2k$ and let $U$ and $W$ be two disjoint sets of $k$ vertices of $G$. Prove that there exist $k$ disjoint paths connecting $U$ and $W$.}


\textbf{Solution:}

\question{}{
Use Theorem 5.21 or 5.22 to show that $\kappa(G) = \lambda(G)$ when $G$ is 3-regular. 
(I'm asking you to reprove  Theorem 5.20, but with a different proof. Copying the proof in the book
and not using Theorems 5.21 or 5.22 is not an acceptable solution.)
}


\textbf{Solution:}

\question{}{
Let $u$ and $v$ be two vertices in an oriented graph $G$.
Describe an algorithm to find the maximum number of internally disjoint $u-v$ paths (paths starting at $u$ and ending in $v$). 
(Hint: Use network flows. How to make sure every vertex is used only in one path?)
}


\textbf{Solution:}

\question{Augmenting paths}{
Consider the network below with given capacity and flow values. (The  edge label $f,u$ means flow-value $f$ and capacity $u$.) 
Find a sequence of augmenting paths and augment the flow to a maximum flow.
\begin{center}
\tikzset{insep/.style={inner sep=2pt, outer sep=0pt, circle, fill},}
\begin{tikzpicture}[scale=2]
\draw
(0,0) node[insep,label=left:$s$](s){}
(1,1) node[insep,label=left:$ $](a){}
(1,0) node[insep,label=left:$ $](b){}
(1,-1) node[insep,label=left:$ $](c){}
(2,1) node[insep,label=left:$ $](d){}
(2,0) node[insep,label=left:$ $](e){}
(2,-1) node[insep,label=left:$ $](f){}
(3,0) node[insep,label=right:$t$](t){}
;
\foreach \x/\y/\n in {s/a/{3,3}, a/d/{3,7}, d/t/{2,2}, s/b/{1,4}, b/e/{1,1}, e/t/{1,8}, b/f/{0,2}}{
\draw[-triangle 45](\x) -- node[above]{\n} (\y);
}
\foreach \x/\y/\n in {s/c/{2,8}, c/f/{2,4}, f/t/{3,6}}{
\draw[-triangle 45](\x) -- node[below]{\n} (\y);
}
\foreach \x/\y/\n in {c/b/{0,2}, b/a/{0,3}, d/e/{1,5}, e/f/{1,1}}{
\draw[-triangle 45](\x) -- node[right]{\n} (\y);
}
\end{tikzpicture}
\end{center}
}


\textbf{Solution:}


\question{Combining cuts}{
Let $(G,u, s, t)$ be a network, and let $\delta^+(X)$ and $\delta^+(Y)$ be minimum $s$-$t$-cuts in $(G,u)$. Show that $\delta^+(X\cap Y)$ and $\delta+(X \cup Y)$ are also minimum $s$-$t$-cuts in $(G,u)$.
}

\textbf{Solution:}




\end{document}














