%  Problem set 5: solutions
%  Combinatorial Optimization, SUAMI, summer 2015
%  Brian Kell <bkell@cmu.edu>

\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=5.5truein \vsize=9truein
\pdfhorigin=1.5truein \pdfvorigin=1truein

% MetaPost stuff
\input supp-pdf
\def\fig#1{\convertMPtoPDF{#1}{1}{1}}
\def\midfig#1{{%
	\setbox0=\hbox{\fig{#1}}%
	\dimen0=0.5\ht0%
	\advance\dimen0 by-0.3\ht\strutbox
	\lower\dimen0\box0%
}}

% AMSFonts
\input amssym.tex

\font\titlefont=cmbx12  \font\smfont=cmr8  \font\transposefont=cmss8 at6pt

\newcount\pno \pno=0
\def\problem{\global\advance\pno by1%
	\medbreak\noindent{\llap{\bf\the\pno.\enspace}}\ignorespaces}
\def\solution{\medskip\noindent\llap{$\triangleright$\bf\phantom.\enspace}{\bf Solution.}\enspace\ignorespaces}

% Pilfered from an example on page 106 of the TeXbook
\def\qed{{\unskip\nobreak\hfil\penalty50
	\hskip1em\hbox{}\nobreak\hfil\hbox{\vrule\vbox to6pt{\hrule\hbox to5.2pt{\hss}\vfil\hrule}\vrule}
	\parfillskip=0pt \finalhyphendemerits=0 \par}}
\def\subqed{{\unskip\nobreak\hfil\penalty50
	\hskip1em\hbox{}\nobreak\hfil\raise2pt\hbox{\vrule height4pt width4pt depth0pt}
	\parfillskip=0pt \finalhyphendemerits=0 \par}}

\newdimen\pivotwidth  \newdimen\pivotdepth
\def\pivot#1{%
	\setbox0=\hbox{\vphantom/$#1$}
	\pivotdepth=\dp0
	\setbox0=\hbox{\vbox{\vskip1pt\hbox{\hskip2pt\box0\hskip2pt}\vskip1pt}}%
	\pivotwidth=\wd0  \advance\pivotwidth by0.8pt
	\lower\pivotdepth\hbox{\vbox{%
		\vskip-1.4pt
		\hrule width\pivotwidth height0.4pt depth0.0pt
		\hbox{%
			\vrule height\ht0 depth\dp0 width0.4pt
			\copy0
			\vrule height\ht0 depth\dp0 width0.4pt
		}%
		\hrule width\pivotwidth height0.4pt depth0.0pt
		\vskip-1.4pt
	}\hskip-2.4pt}%
}

\def\frac#1#2{{\textstyle{{#1}\over{#2}}}}
\def\R{{\mathord{\Bbb R}}}  \def\Q{{\mathord{\Bbb Q}}}
\def\Z{{\mathord{\Bbb Z}}}  \def\N{{\mathord{\Bbb N}}}
\def\transpose{{\raise0.5pt\hbox{\transposefont T}}}
\def\labs{\mathopen|}  \def\rabs{\mathclose|}  \def\abs#1{\labs#1\rabs}
\def\implies{\Longrightarrow}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\centerline{\titlefont Combinatorial Optimization}
\smallskip
\centerline{\bf Problem set~5: solutions}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Consider the problem of determining the least expensive way to
complete a project by a given deadline. When the linear program is formulated,
the objective function has a constant term. For instance, if activities A,~B,
and~C have usual times of 8,~5, and 7~days and can be sped up at a cost of
\$200,~\$150, and \$225 per day, respectively, then the objective function
(i.e., the total speedup cost) is
$$200(8-d_{\rm A})+150(5-d_{\rm B})+225(7-d_{\rm C}),$$
where $d_{\rm A}$,~$d_{\rm B}$, and~$d_{\rm C}$ are duration variables for the
three activities. When expanded, this objective function becomes
$$3925-200d_{\rm A}-150d_{\rm B}-225d_{\rm C},$$
which has the constant term~3925. Describe a way to handle an objective
function with a constant term in the simplex algorithm.

\solution Here are three possible ways to handle an objective function with a
constant term in the simplex algorithm. For an illustration, we will use the
following maximization LP (because we discussed the simplex algorithm as a
maximization algorithm):
$$\eqalign{
	{\rm maximize}\quad3x_1+5x_2+17&\cr
	{\rm subject\ to}\quad\phantom1x_1+\phantom1x_2\phantom{{}+00}&\le\phantom08\cr
	2x_1+\phantom1x_2\phantom{{}+00}&\le12\cr
	&\phantom{{}=00}\llap{$x_1\ge0$,\quad$x_2\ge0$}.\cr
}$$

\smallskip

\item{1.} Replace the constant term with a variable~$K$ and add an equality
constraint to force $K$ to have the correct value:
$$\eqalign{
	{\rm maximize}\quad3x_1+5x_2+K&\cr
	{\rm subject\ to}\quad\phantom1x_1+\phantom1x_2\phantom{{}+K}&\le\phantom08\cr
	2x_1+\phantom1x_2\phantom{{}+K}&\le12\cr
	K&=17\cr
	&\phantom{{}=00}\llap{$x_1\ge0$,\quad$x_2\ge0$,\quad$K\ge0$}.\cr
}$$

\smallskip

\item{2.} In the equation represented by the objective row in the initial
simplex tableau, the constant term will appear on the right-hand side. In the
example here, we have $z=3x_1+5x_2+17$, so the equation represented by the
objective row in the initial simplex tableau will be $-3x_1-5x_2+z=17$. So,
when writing the initial simplex tableau, enter the constant term at the top of
the RHS column (instead of zero):
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut$#$&\quad\hfil\strut$#$&\quad\hfil\strut$#$%
	&\quad\hfil\strut$#$&\quad\hfil\strut$#$\quad&\vrule#&\quad\hfil\strut$#$\quad\cr
x_1&x_2&s_1&s_2&z&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
-3&-5&0&0&1&&17\cr
\omit&\omit&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&height2pt\cr
1&1&1&0&0&&8\cr
2&1&0&1&0&&12\cr}}$$

\smallskip

\item{3.} Ignore the constant term entirely during the simplex algorithm and
just remember to add it to the optimal objective value at the end. For the
example, solve the following linear program instead, and then add~17 to the
optimal objective value:
$$\eqalignno{
	{\rm maximize}\quad3x_1+5x_2&\cr
	{\rm subject\ to}\quad\phantom1x_1+\phantom1x_2&\le\phantom08\cr
	2x_1+\phantom1x_2&\le12\cr
	&\phantom{{}=00}\llap{$x_1\ge0$,\quad$x_2\ge0$}.&\hbox{\qed}\cr
}$$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem What is the greatest possible number of critical paths in a project
with $n$~activities? Describe a family of examples for infinitely many values
of~$n$ that attain this number of critical paths.

\solution Consider a project with $n$~activities. We shall make the following
assumptions: First, there are no circular dependencies, so that the CPM network
contains no directed cycles (i.e., it is a directed acyclic graph). This is a
reasonable assumption, because if a project contains circular dependencies
among its activities then it can never be completed. Second, all project
durations are positive (specifically, nonzero). This is also a reasonable
assumption for real-world projects.

Define an {\it activity chain\/} to be a sequence $(a_1,a_2,\ldots,a_r)$ of
activities such that $a_i$~is an immediate prerequisite of~$a_{i+1}$ for all
$1\le i<r$. Then a critical path is an activity chain such that the total
duration of $a_1$,~$a_2$, \dots,~$a_r$ is {\it maximized}. Observe that because
we are assuming that all project durations are positive, no proper subsequence
of a critical path is itself a critical path.

Partition the set of activities as follows: Let $A_1$ be the set of all
activities having no prerequisites, and for $i\ge2$ let $A_i$ be the set of all
activities not in $\bigcup_{j=1}^{i-1}A_j$ all of whose prerequisites are in
$\bigcup_{j=1}^{i-1}A_j$. Let $k$ be the number of nonempty subsets of
activities constructed in this way (so $A_1$,~$A_2$, \dots,~$A_k$ is a
partition of the set of activities). Because the project has no circular
dependencies, every activity is an element of one of these subsets~$A_i$. Also,
for $i\ge2$, every activity in~$A_i$ has at least one immediate prerequisite
in~$A_{i-1}$ (otherwise all of its prerequisites would be in
$\bigcup_{j=1}^{i-2}A_j$, so it would not be in~$A_i$; it would be in~$A_j$ for
some $j<i$).

\proclaim Lemma. Let $a_i\in A_i$ and $a_j\in A_j$ for some $j\ge i+2$. If
there exists a critical path~$P$ in which $a_i$ is immediately followed
by~$a_j$, then for every $i<h<j$ there exists $a_h\in A_h$ such that no
critical path includes both $a_i$~and~$a_h$.

\noindent{\bf Proof.}\enspace For $h=j-1,j-2,\ldots,i+1$, let $a_h$ be an
immediate predecessor of~$a_{h+1}$ in~$A_{h+1}$. Suppose for the sake of
contradiction that there exists $i<h<j$ such that both $a_i$~and~$a_h$ are
included in some critical path~$P'$. But then the portion of~$P$ ending
with~$a_i$, followed by the portion of~$P'$ from $a_i$ to~$a_h$, followed by
$(a_{h+1},a_{h+2},\ldots,a_j)$, followed by the portion of~$P$ after~$a_j$,
yields an activity chain, and the total duration of this activity chain is
strictly larger than that of~$P$ because $P$~is a proper subsequence. This
contradicts the fact that $P$ is a critical path. \subqed

\proclaim Lemma. If $a$ is the last activity in a critical path~$P$, then no
critical path contains $a$~followed by another activity~$a'$.

\noindent{\bf Proof.}\enspace Otherwise appending~$a'$ to~$P$ would produce an
activity chain with strictly larger total duration. \subqed

\proclaim Corollary. The number of critical paths is bounded above by
$\abs{A_1}\cdot\abs{A_2}\cdot\cdots\cdot\abs{A_k}$.

\noindent{\bf Proof.}\enspace Observe that every critical path has the form of
a sequence of activities produced by choosing one activity from~$A_1$, followed
by zero or one activity from~$A_2$, followed by zero or one activity
from~$A_3$, \dots, followed by zero or one activity from~$A_k$. (Not all such
sequences of activities are critical paths, or even just {\it paths\/} in the
CPM network, but all critical paths have this form.) So every critical path
(along with possibly some other sequences of activities) can be constructed as
a sequence~$S$ of activities in the following way:

\smallskip

\item{0.} Initialize $S$ to be the empty sequence.

\smallskip

\item{1.} Choose one activity $a_1\in A_1$ and append $a_1$ to~$S$.

\smallskip

\item{2.} Optionally, choose one activity $a_2\in A_2$ and append $a_2$ to~$S$.

\smallskip

\item{3.} Optionally, choose one activity $a_3\in A_3$ and append $a_3$ to~$S$.

\smallskip

\item{} $\vdots$

\smallskip

\item{$k$.} Optionally, choose one activity $a_k\in A_k$ and append $a_k$
to~$S$.

\smallbreak

\noindent There are $\abs{A_1}$~ways to perform step~1. For $2\le i\le k$,
there are $\abs{A_i}+1$ ways to perform step~$i$ (one of which is to skip the
step, i.e., choose zero activities from~$A_i$). But by the two preceding
lemmas, if, given a partially constructed sequence~$S$ after steps
1~through~$i-1$, there is a way to extend~$S$ to a critical path by skipping
step~$i$, then there exists at least one activity $a_i\in A_i$ such that
appending~$a_i$ to~$S$ {\it cannot\/} produce a critical path. Therefore, given
any combination of ways to perform the first $i-1$ steps, there are at most
$(\abs{A_i}+1)-1=\abs{A_i}$ ways to perform the $i$th step that will lead to a
critical path. Hence there are no more than
$\abs{A_1}\cdot\abs{A_2}\cdot\cdots\cdot\abs{A_k}$ critical paths in all.
\subqed

\medbreak

\noindent Now observe that $\sum_{i=1}^k\abs{A_i}=n$, because each activity is
in exactly one of the subsets~$A_i$. So the question becomes: How can $n$ be
expressed as a sum of positive integers having the greatest possible product?

\proclaim Theorem. For a fixed positive integer value of~$n$, if\/
$\sum_{i=1}^kc_i=n$ for positive integers~$c_i$, then the maximum value of\/
$\prod_{i=1}^kc_i$ is
$$\cases{
	1,&if\/ $n=1$;\cr
	3^m,&if\/ $n=3m$;\cr
	4\cdot3^{m-1},&if\/ $n=3m+1\ge4$;\cr
	2\cdot3^m,&if\/ $n=3m+2$.\cr
}$$

\noindent{\bf Proof.}\enspace The cases $n\in\{1,2,3,4\}$ are easy to verify by
inspection.

If $n\ge5$, then $2(n-2)=2n-4>n$, so writing $n$ as the single-term sum~$n$ is
not optimal, because writing it as $2+(n-2)$ produces a strictly larger
product. Suppose $n$ is written as a sum $c_1+c_2+\cdots+c_k$ of positive
integers, with $k\ge2$. If any term~$c_i$ is greater than~4, then $c_i$ can be
replaced by a sum of smaller positive integers whose product is greater
than~$c_i$ [e.g., $2+(c_i-2)$], so such a sum cannot be optimal. If any
term~$c_i$ is~1, then that term can be removed and another term increased by~1,
which will strictly increase the product, so a sum containing the term~1 cannot
be optimal either. If the sum contains three terms that are~2, then those terms
can be replaced by $3+3$, which will strictly increase the product (because
$3\times3>2\times2\times2$), so a sum containing three or more 2's also cannot
be optimal. Lastly, if any term~$c_i$ is~4, then that term can be replaced by
$2+2$ without changing the product. Therefore, there is an optimal sum
consisting solely of 2's~and~3's, with no more than two~2's. Consequently, for
$n\ge5$, an optimal sum is
$$\vbox{\offinterlineskip
\ialign{$#\hfil$&\quad#\hfil\cr
	\underbrace{\vphantom(3+\cdots+3}_{m\rm\ terms},&if\/ $n=3m$;\cr
	\noalign{\medskip}
	2+2+\underbrace{\vphantom(3+\cdots+3}_{m-1\rm\ terms},&if\/ $n=3m+1$;\cr
	\noalign{\medskip}
	2+\underbrace{\vphantom(3+\cdots+3}_{m\rm\ terms},&if\/ $n=3m+2$.\cr
}}\eqno\hbox{\subqed}$$

\noindent Thus the number of critical paths in a project with $n$~activities is
bounded by the expression in this theorem. Moreover, this bound can be
achieved as follows.

\smallskip

\item{$\bullet$} For $n=1$, any project with a single activity (necessarily
having no prerequisites) has one critical path.

\smallskip\filbreak

\item{$\bullet$} For $n=3m$, a project of the following form has $3^m$~critical
paths.
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut#\hfil\quad&&\hfil\strut#\hfil\quad\cr
&Immediate\cr
Activity&prerequisites&Duration\cr
\noalign{\vskip2pt\hrule\vskip2pt}
$a_1$&---&1\cr
$a_2$&---&1\cr
$a_3$&---&1\cr
\noalign{\smallskip}
$a_4$&$a_1$,~$a_2$,~$a_3$&1\cr
$a_5$&$a_1$,~$a_2$,~$a_3$&1\cr
$a_6$&$a_1$,~$a_2$,~$a_3$&1\cr
\noalign{\smallskip}
$a_7$&$a_4$,~$a_5$,~$a_6$&1\cr
$a_8$&$a_4$,~$a_5$,~$a_6$&1\cr
$a_9$&$a_4$,~$a_5$,~$a_6$&1\cr
\noalign{\smallskip}
$\vdots$&$\vdots$&$\vdots$\cr
\noalign{\smallskip}
$a_{3m-2}$&$a_{3m-5}$,~$a_{3m-4}$,~$a_{3m-3}$&1\cr
$a_{3m-1}$&$a_{3m-5}$,~$a_{3m-4}$,~$a_{3m-3}$&1\cr
$a_{3m}$&$a_{3m-5}$,~$a_{3m-4}$,~$a_{3m-3}$&1\cr
}}$$
The CPM network of a project of this form is shown below.
$$\fig{pset05-solns-cpm-1.mps}$$
All activities have duration~1, and therefore, as a consequence of the
structure of the project, every activity is critical. Hence any path from the
beginning of the project to the end is a critical path. There are
$m$~``layers'' in this CPM network: these are the sets $A_1=\{a_1,a_2,a_3\}$,
$A_2=\{a_4,a_5,a_6\}$, \dots, $A_m=\{a_{3m-2},a_{3m-1},a_{3m}\}$. Each of these
layers contains three activities, so there are $3^m$~critical paths.

\smallskip\filbreak

\item{$\bullet$} For $n=3m+1\ge4$, a project of the following form has
$4\cdot3^{m-1}$ critical paths.
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut#\hfil\quad&&\hfil\strut#\hfil\quad\cr
&Immediate\cr
Activity&prerequisites&Duration\cr
\noalign{\vskip2pt\hrule\vskip2pt}
$a_1$&---&1\cr
$a_2$&---&1\cr
\noalign{\smallskip}
$a_3$&$a_1$,~$a_2$&1\cr
$a_4$&$a_1$,~$a_2$&1\cr
\noalign{\smallskip}
$a_5$&$a_3$,~$a_4$&1\cr
$a_6$&$a_3$,~$a_4$&1\cr
$a_7$&$a_3$,~$a_4$&1\cr
\noalign{\smallskip}
$a_8$&$a_5$,~$a_6$,~$a_7$&1\cr
$a_9$&$a_5$,~$a_6$,~$a_7$&1\cr
$a_{10}$&$a_5$,~$a_6$,~$a_7$&1\cr
\noalign{\smallskip}
$a_{11}$&$a_8$,~$a_9$,~$a_{10}$&1\cr
$a_{12}$&$a_8$,~$a_9$,~$a_{10}$&1\cr
$a_{13}$&$a_8$,~$a_9$,~$a_{10}$&1\cr
\noalign{\smallskip}
$\vdots$&$\vdots$&$\vdots$\cr
\noalign{\smallskip}
$a_{3m-1}$&$a_{3m-4}$,~$a_{3m-3}$,~$a_{3m-2}$&1\cr
$a_{3m}$&$a_{3m-4}$,~$a_{3m-3}$,~$a_{3m-2}$&1\cr
$a_{3m+1}$&$a_{3m-4}$,~$a_{3m-3}$,~$a_{3m-2}$&1\cr
}}$$
The CPM network of a project of this form is shown below.
$$\hss\fig{pset05-solns-cpm-2.mps}\hss$$
Again, every activity is critical, so any path from the beginning of the
project to the end is a critical path. There are $m+1$~``layers'' in this CPM
network; the first two layers contain two activities each, and the remaining
$m-1$~layers contain three activities each, so there are
$4\cdot3^{m-1}$~critical paths.

\smallskip\filbreak

\item{$\bullet$} For $n=3m+2$, a project of the following form has
$2\cdot3^m$~critical paths.
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut#\hfil\quad&&\hfil\strut#\hfil\quad\cr
&Immediate\cr
Activity&prerequisites&Duration\cr
\noalign{\vskip2pt\hrule\vskip2pt}
$a_1$&---&1\cr
$a_2$&---&1\cr
\noalign{\smallskip}
$a_3$&$a_1$,~$a_2$&1\cr
$a_4$&$a_1$,~$a_2$&1\cr
$a_5$&$a_1$,~$a_2$&1\cr
\noalign{\smallskip}
$a_6$&$a_3$,~$a_4$,~$a_5$&1\cr
$a_7$&$a_3$,~$a_4$,~$a_5$&1\cr
$a_8$&$a_3$,~$a_4$,~$a_5$&1\cr
\noalign{\smallskip}
$a_9$&$a_6$,~$a_7$,~$a_8$&1\cr
$a_{10}$&$a_6$,~$a_7$,~$a_8$&1\cr
$a_{11}$&$a_6$,~$a_7$,~$a_8$&1\cr
\noalign{\smallskip}
$\vdots$&$\vdots$&$\vdots$\cr
\noalign{\smallskip}
$a_{3m}$&$a_{3m-3}$,~$a_{3m-2}$,~$a_{3m-1}$&1\cr
$a_{3m+1}$&$a_{3m-3}$,~$a_{3m-2}$,~$a_{3m-1}$&1\cr
$a_{3m+2}$&$a_{3m-3}$,~$a_{3m-2}$,~$a_{3m-1}$&1\cr
}}$$
The CPM network of a project of this form is shown below.
$$\hss\fig{pset05-solns-cpm-3.mps}\hss$$
Again, every activity is critical, so any path from the beginning of the
project to the end is a critical path. There are $m+1$~``layers'' in this CPM
network; the first layer contains two activities, and the remaining $m$~layers
contain three activities each, so there are $2\cdot3^m$~critical paths. \qed

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Consider a directed graph~$G=(V,E)$ with nonnegative edge weights
$c_{ij}\ge0$ and specified nodes $s,t\in V$. For each node $i\in V$, let
$\pi_i$ be the distance of a shortest (directed) path from $i$ to~$t$. (Assume
that every node~$i$ has such a path to~$t$.) Show that $\pi$ is an optimal
feasible solution to the dual of the node-arc LP formulation for the shortest
path problem on~$G$ from $s$ to~$t$. Is the assumption $c_{ij}\ge0$ necessary?

\solution The dual of the node-arc LP formulation for the shortest path problem
on~$G$ from $s$ to~$t$ is as follows:
$$\eqalign{
	{\rm maximize}\quad&\pi_s-\pi_t\cr
	{\rm subject\ to}\quad&\pi_i-\pi_j\le c_{ij}
		\quad\hbox{for all arcs $(i,j)\in E$}\cr
	&\hbox{all variables unrestricted.}\cr
}$$

\noindent For each node $i\in V$, let $\pi_i$ be the shortest distance from $i$
to~$t$. Then for each arc $(i,j)\in E$, the constraint $\pi_i\le\pi_j+c_{ij}$
is satisfied, because the shortest distance from $i$ to~$t$ cannot be greater
than the shortest distance from $j$ to~$t$ plus the length of the arc joining
$i$~and~$j$ (by the triangle inequality). In more detail, we know that there
exists a directed path $(j=w_0,w_1,w_2,\ldots,w_k=t)$ from $j$ to~$t$ of total
distance $\sum_{p=0}^{k-1}c_{w_pw_{p+1}}=\pi_j$. So
$(i,j,w_1,w_2,\ldots,w_{k-1},t)$ is a directed walk from $i$ to~$t$ of total
distance $c_{ij}+\pi_j$. This implies that there is a directed path from $i$
to~$t$ of total distance no greater than $c_{ij}+\pi_j$, which means that the
{\it shortest\/} distance~$\pi_i$ from $i$ to~$t$ cannot be greater than this.
Therefore, all of the constraints are satisfied by this solution~$\pi$. Clearly
the domains place no restrictions on~$\pi$, so $\pi$ is a feasible solution.

Now consider any (directed) path $P=(s=v_0,v_1,v_2,\ldots,v_{l-1},v_l=t)$ from
$s$ to~$t$. Add the corresponding constraints:
$$\eqalign{
	\pi_s-\pi_{v_1}\phantom{{}+\pi_{v_2}+\pi_{v_3}+\ddots+\pi_{v_{l-1}}-\pi_t}&\le c_{sv_1}\cr
	\pi_{v_1}-\pi_{v_2}\phantom{{}+\pi_{v_3}+\ddots+\pi_{v_{l-1}}-\pi_t}&\le c_{v_1v_2}\cr
	\pi_{v_2}-\pi_{v_3}\phantom{{}+\ddots+\pi_{v_{l-1}}-\pi_t}&\le c_{v_2v_3}\cr
	\ddots\phantom{{}+\pi_{v_{l-1}}-\pi_t}&{\setbox0=\hbox{${}\le{}$}\hbox to\wd0{\hss$\vdots$\hss}}\cr
	\pi_{v_{l-1}}-\pi_t&\le c_{v_{l-1}t}\cr
	\noalign{\smallskip\hrule\smallskip}
	\quad\pi_s\phantom{{}+\pi_{v_1}+\pi_{v_2}+\pi_{v_3}+\ddots+\pi_{v_{l-1}}}-\pi_t
		&\le\sum_{p=0}^{l-1}c_{v_pv_{p+1}}.\quad\cr
}$$
The expression on the right-hand side of the resulting inequality is the length
of the path~$P$. Therefore, the objective value $\pi_s-\pi_t$ cannot be greater
than the length of~$P$. Since $P$ was an arbitrary path from $s$ to~$t$, the
value of $\pi_s-\pi_t$ cannot be greater than the length of {\it any\/} path
from $s$ to~$t$; in particular, it cannot be greater than the length of a
{\it shortest\/} path from $s$ to~$t$. So the solution~$\pi$ given in this
problem, in which $\pi_s$ is the length of a shortest path from $s$ to~$t$ and
$\pi_t$~is zero, must be optimal.

No part of the reasoning above used the assumption that $c_{ij}\ge0$, so this
assumption is not necessary. However, if there is a {\it cycle\/} with
negative total weight $\bigl[$say,
$(v_0,v_1,v_2,\ldots,\allowbreak v_{k-1},v_k=v_0)$ with
$\sum_{i=0}^{k-1}c_{v_iv_{i+1}}=C<0\bigr]$, then we can add the corresponding
constraints to get
$$\eqalign{
	\pi_{v_0}-\pi_{v_1}\phantom{{}+\pi_{v_2}+\pi_{v_3}+\ddots+\pi_{v_{k-2}}-\pi_{v_{k-1}}}&\le c_{iv_1}\cr
	\pi_{v_1}-\pi_{v_2}\phantom{{}+\pi_{v_3}+\ddots+\pi_{v_{k-2}}-\pi_{v_{k-1}}}&\le c_{v_1v_2}\cr
	\pi_{v_2}-\pi_{v_3}\phantom{{}+\ddots+\pi_{v_{k-2}}-\pi_{v_{k-1}}}&\le c_{v_2v_3}\cr
	\ddots\phantom{{}+\pi_{v_{k-2}}-\pi_{v_{k-1}}}&{\setbox0=\hbox{${}\le{}$}\hbox to\wd0{\hss$\vdots$\hss}}\cr
	\pi_{v_{k-2}}-\pi_{v_{k-1}}&\le c_{v_{k-2}v_{k-1}}\quad\cr
	\quad{-}\pi_{v_0}\phantom{{}+\pi_{v_1}+\pi_{v_2}+\pi_{v_3}+\ddots+\pi_{v_{k-2}}}+\pi_{v_{k-1}}&\le c_{v_{k-1}v_0}\cr
	\noalign{\smallskip\hrule\smallskip}
	0&\le C,\cr
}$$
which is a contradiction, so the dual LP is infeasible. (Note that this is a
consequence of the fact that the primal is unbounded.)

Therefore the statement in the problem is still true and meaningful when the
assumption $c_{ij}\ge0$ is removed, as long as there are no cycles with
negative total weight. \qed

\filbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\figuregap{\vskip0pt plus12pt}

\problem Use Dijkstra's algorithm (or the primal-dual algorithm) to find a
shortest path from $s$ to~$t$ in the following undirected graph.
$$\fig{pset05-4.mps}$$

\solution We show the iterations of Dijkstra's algorithm in the figures below.
In each figure, the edge weights are circled, the vertex labels (denoting the
tentative distance from~$s$) are shown in red, the current set~$W$ of vertices
whose distances from~$s$ have definitely been determined is outlined in light
blue, and the vertex~$x$ outside~$W$ with the smallest vertex label is boxed
in green.

\figuregap

$$\fig{pset05-solns-dijkstra-1.mps}$$

\figuregap

$$\fig{pset05-solns-dijkstra-2.mps}$$

\figuregap

$$\fig{pset05-solns-dijkstra-3.mps}$$
(Note: At this stage $c$~and~$d$ tie for the minimum vertex label. Here we
chose $x=d$ arbitrarily, but it is equally valid to choose $x=c$.)

\goodbreak\figuregap

$$\fig{pset05-solns-dijkstra-4.mps}$$

\figuregap

$$\fig{pset05-solns-dijkstra-5.mps}$$

\figuregap

$$\fig{pset05-solns-dijkstra-6.mps}$$

\figuregap

$$\fig{pset05-solns-dijkstra-7.mps}$$

\figuregap

$$\fig{pset05-solns-dijkstra-8.mps}$$

\figuregap

$$\fig{pset05-solns-dijkstra-9.mps}$$

\figuregap

Now all vertices are included in~$W$, so the labels give the shortest distance
from~$s$ for each vertex. To find a shortest path from~$s$ to any vertex, we
identify the admissible edges, which are those edges whose weight equals the
difference of the vertex labels at their endpoints. The admissible edges are
shown as double green lines in the figure below.
$$\fig{pset05-solns-dijkstra-10.mps}$$
From this figure, we see that there are four shortest paths from $s$ to~$t$:
$s$--$a$--$c$--$e$--$t$, $s$--$a$--$c$--$f$--$t$, $s$--$b$--$c$--$e$--$t$,
and $s$--$b$--$c$--$f$--$t$. Each of these paths has total weight~34.

\goodbreak

Alternatively, we can use the primal-dual algorithm directly. The figures
below show the iterations of the primal-dual algorithm. In each figure, the
values of the dual solution~$\pi$ are written in green above each vertex, the
admissible edges~$J$ are drawn as double green lines, the set~$W$ of vertices
from which $t$ is reachable using only edges in~$J$ is outlined in light blue,
the values of the optimal solution~$\bar\pi$ to the dual of the restricted
primal are written in red below each vertex, the candidate edges~$K$ are drawn
with red hash marks, and the values of $c_{ij}-(\pi_i-\pi_j)$ are written in
blue below the candidate edges. The value of~$\theta_1$, which is the minimum
value of $c_{ij}-(\pi_i-\pi_j)$ over all candidate edges, is shown to the
lower right of the figure; this is the amount by which the dual values will be
increased for all vertices not in~$W$.

\figuregap

$$\fig{pset05-solns-primaldual-1.mps}$$

\figuregap

$$\fig{pset05-solns-primaldual-2.mps}$$

\figuregap

$$\fig{pset05-solns-primaldual-3.mps}$$

\figuregap

$$\fig{pset05-solns-primaldual-4.mps}$$

\figuregap

$$\fig{pset05-solns-primaldual-5.mps}$$

\figuregap

$$\fig{pset05-solns-primaldual-6.mps}$$

\figuregap

$$\fig{pset05-solns-primaldual-7.mps}$$

\figuregap

$$\fig{pset05-solns-primaldual-8.mps}$$

\figuregap

$$\fig{pset05-solns-primaldual-9.mps}$$

At this stage $t$~is reachable from~$s$ using only edges in~$J$, so the optimal
solution to the dual of the restricted primal is $\bar\pi=0$, which indicates
that the current dual solution is optimal. Therefore, the shortest distance
from $s$ to~$t$ is~34, and any path from $s$ to~$t$ using only admissible edges
is a shortest path. Again we see that there are four such paths:
$s$--$a$--$c$--$e$--$t$, $s$--$a$--$c$--$f$--$t$, $s$--$b$--$c$--$e$--$t$, and
$s$--$b$--$c$--$f$--$t$. \qed

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Give an example of a simple graph with at least two vertices such that
no two vertices have the same degree, or explain why this is impossible.

\solution This is impossible for a finite graph. Suppose that $G=(V,E)$ is a
simple finite graph with $\abs V=n\ge2$ such that no two vertices have the same
degree. The possible vertex degrees in~$G$ are 0,~1, 2, \dots, $n-1$, so, since
all $n$~vertices of~$G$ have different degrees, each one of these possible
degrees must occur exactly once. Therefore $G$ contains a vertex~$u$ of
degree~0 and also a vertex~$v$ of degree~$n-1$. These are not the same vertex,
because $n\ge2$ (so $n-1\not=0$). Now the vertex~$v$ must be adjacent to every
other vertex, including~$u$. On the other hand, the vertex~$u$ cannot be
adjacent to any other vertex, including~$v$. This is a contradiction, so such a
graph cannot exist.

However, it {\it is\/} possible if we consider graphs with infinitely many
vertices. For example, here is a graph on the vertex set $\N=\{0,1,2,\ldots\}$
in which each vertex~$n$ has degree~$n$:
$$\fig{pset05-solns-tree.mps}$$
Ignoring the isolated vertex~0, this graph is a rooted tree on the vertex
set~$\N$ in which 1~is the root and has exactly one child, and every vertex~$n$
other than~1 has exactly $n-1$ children.

\goodbreak

\def\phiround#1{[\![#1]\!]}

Here is another construction of a graph on the vertex set~$\N$ in which each
vertex~$n$ has degree~$n$; this construction has a very close connection to the
golden ratio. Let $\phi=(\sqrt5-1)/2=0.618\ldots$ and
$\Phi=(\sqrt5+1)/2=1.618\ldots\,$. Note that $\phi$~and~$\Phi$ are irrational,
and they satisfy the equations $\Phi=\phi+1$ and $\phi=1/\Phi$. For
$0\le x\in\R$, define
$$\phiround x=\cases{
	\lfloor x\rfloor,&if $x-\lfloor x\rfloor<1-\phi$;\cr
	\lceil x\rceil,&if $x-\lfloor x\rfloor>1-\phi$.\cr
}$$
In other words, $\phiround{x}$~rounds $x$ down if the fractional part of~$x$
is less than $1-\phi$ and up if the fractional part is greater than $1-\phi$.
For our purposes, we need not define what happens if the fractional part is
equal to $1-\phi$, because we are going to be applying the
function~$\phiround{{}\cdot{}}$ only to expressions of the form
$\phi n$~and~$\Phi n$ for $n\in\N$. For all $n\in\N$ we have
$\phi n-\lfloor\phi n\rfloor\not=1-\phi$, for if
$\phi n-\lfloor\phi n\rfloor=1-\phi$ then
$\lfloor\phi n\rfloor=\phi n+\phi-1=\phi(n+1)-1$, and hence $\phi(n+1)\in\Z$,
which cannot be true because $\phi\notin\Q$. Likewise, for all $n\in\N$ we have
$\Phi n-\lfloor\Phi n\rfloor\not=1-\phi$, for if
$\Phi n-\lfloor\Phi n\rfloor=1-\phi$ then
$\lfloor\Phi n\rfloor=\Phi n+\phi-1=\Phi n+\Phi-2=\Phi(n+1)-2$, and hence
$\Phi(n+1)\in\Z$, which cannot be true because $\Phi\notin\Q$. Therefore,
$\phiround{\phi n}$~and~$\phiround{\Phi n}$ are well defined for all $n\in\N$.

Next we see that for $m,n\in\N$, $m\ge\phiround{\phi n}$ if and only~if
$n\le\phiround{\Phi m}$. Note that $\phiround x=k$ if and only~if
$k-\phi<x<k+1-\phi$. So
$$\eqalign{
	m\ge\phiround{\phi n}&\iff\phi n<m+1-\phi\cr
	&\iff n<\Phi(m+1-\phi)\cr
	&\iff n<\Phi m+\Phi-1\cr
	&\iff n<\Phi m+\phi\cr
	&\iff n-\phi<\Phi m\cr
	&\iff n\le\phiround{\Phi m}.\cr
}$$

\noindent Now, for $n\in\N$, define the neighborhood of~$n$ to be the set
$$N(n)=\bigl\{\,m\in\N:\phiround{\phi n}\le m\le\phiround{\Phi n}\,\bigr\}\setminus\{n\}.$$
Observe that $\Phi n=(1+\phi)n=n+\phi n$, so the fractional parts of
$\phi n$~and~$\Phi n$ are equal. Therefore the function~$\phiround{{}\cdot{}}$
rounds $\phi n$~and~$\Phi n$ either both up or both down, which means that
$\phiround{\Phi n}-\phiround{\phi n}=\Phi n-\phi n=(\Phi-\phi)n=n$. The
endpoints of the interval $\bigl[\,\phiround{\phi n},\phiround{\Phi n}\,\bigr]$
are nonnegative integers, so this interval contains $n+1$~elements of~$\N$,
and then we remove~$n$ to form~$N(n)$. So $\abs{N(n)}=n$.

Finally, for $m,n\in\N$, we have $m\in N(n)$ if and only~if $n\in N(m)$,
because for $m\not=n$,
$$m\in N(n)\iff\phiround{\phi n}\le m\le\phiround{\Phi n}
	\iff\phiround{\phi m}\le n\le\phiround{\Phi m}\iff n\in N(m).$$
Therefore, the relation~$\sim$ defined on~$\N$ by
$$m\sim n\qquad\hbox{if and only~if}\qquad m\in N(n)$$
is symmetric (and antireflexive), so we may define a graph on the vertex
set~$\N$ by specifying that two vertices $m$~and~$n$ are adjacent if and
only~if $m\in N(n)$. Since $\abs{N(n)}=n$ for all~$n$, each vertex~$n$ has
degree~$n$. \qed

\filbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Let $G=(V,E)$ be a simple undirected graph, and let $n=\abs V$. Prove
that all of the following statements are equivalent.

\smallskip

\item{(a)} $G$~is a tree (that~is, $G$~is connected and acyclic).

\smallskip

\item{(b)} For any two distinct vertices $u,v\in V$, there exists a unique
path in~$G$ between $u$~and~$v$.

\smallskip

\item{(c)} $G$~is minimally connected: $G$~is connected, but if any edge is
removed from~$G$ then the resulting graph is disconnected.

\smallskip

\item{(d)} $G$~is maximally acyclic: $G$~is acyclic, but if any edge is added
joining nonadjacent vertices of~$G$ then the resulting graph has a cycle.

\smallskip

\item{(e)} $G$~is connected and has $n-1$ edges.

\smallskip

\item{(f)} $G$~is acyclic and has $n-1$ edges.

\solution First we prove the following useful counting lemma.

\proclaim Vertices--edges--components lemma. If\/ $G=(V,E)$ is a simple
undirected graph with $n$~vertices and $m$~edges, then $G$ has at least $n-m$
connected components, with equality if and only~if $G$~is acyclic.

\noindent{\bf Proof.}\enspace By induction on~$m$. If $m=0$, then $G$ consists
of $n$~isolated vertices, so it has $n=n-m$ connected components, and clearly
$G$ is acyclic.

Suppose $m\ge1$. Let $e=\{u,v\}\in E$, and consider the graph
$H=(V,E\setminus\{e\})$ formed from~$G$ by removing the edge~$e$. The graph~$H$
has $m-1$~edges, so by induction $H$~has at least $n-m+1$ connected components,
with equality if and only~if $H$~is acyclic.

If $u$~and~$v$ are in the same connected component in~$H$, then $G$ has the
same number of connected components as~$H$, i.e., at least $n-m+1$.
Furthermore, there is a path $(u=w_0,w_1,w_2,\ldots,w_{k-1},w_k=v)$ in~$H$
between $u$~and~$v$, and $k\ge2$ because $u$~and~$v$ are not adjacent in~$H$.
So $(u=w_0,w_1,w_2,\ldots,w_{k-1},w_k=v,u)$ is a cycle in~$G$, which means $G$
is not acyclic.

Otherwise, $u$~and~$v$ are in different connected components in~$H$, so when
the edge $\{u,v\}$ is added to~$H$ to form~$G$, those two connected components
are joined. Hence $G$ has exactly one fewer connected component than~$H$, i.e.,
at least $n-m$ connected components. In this case, the edge $\{u,v\}$ cannot be
part of a cycle in~$G$ (because this would imply a path between $u$~and~$v$
that does not use the edge $\{u,v\}$, which would be a path between $u$~and~$v$
in~$H$), so $G$~is acyclic if and only~if $H$~is acyclic, and therefore $G$ has
$n-m$ connected components if and only~if $G$~is acyclic. \subqed

\medbreak

Now we can begin proving implications among the six statements. More proofs are
presented below than are necessary to prove the equivalence of the six
statements; all that is necessary is to prove a set of implications such that
any statement can be reached from any other statement by following a chain of
implications in the set.

\medskip

\noindent$\rm(a)\implies(b)$.\enspace Suppose $G$ is a tree, i.e., is connected
and acyclic. Let $u,v\in V$ be distinct vertices. Then there exists a path
between $u$~and~$v$, because $G$ is connected. Suppose for the sake of
contradiction that this path is not unique, i.e., that there exist two distinct
paths $(u=w_0,w_1,w_2,\ldots,w_{p-1},w_p=v)$ and
$(u=x_0,x_1,x_2,\ldots,x_{q-1},x_q=v)$ for some $p,q\ge1$. Let $r\ge1$ be the
least positive integer such that $w_r\not=x_r$; such an integer exists because
the two paths are distinct (in particular, $1\le r\le\min\{p,q\}$). Let $s\ge
r$ be the least integer greater than or equal to~$r$ such that $w_s=x_t$ for
some~$t$; such an integer exists because $w_p=v=x_q$. Then
$(w_{r-1},w_r,w_{r+1},\ldots,w_{s-1},w_s=x_t,x_{t-1},\ldots,x_{r-1}=w_{r-1})$
is a cycle, because $w_r$,~$w_{r+1}$, \dots,~$w_{s-1}$ are distinct from
all~$x_i$'s by the definition of~$s$, so no vertices are repeated in this walk
(except the beginning and end, $w_{r-1}=x_{r-1}$). Also, the length of this
walk is at least~3: we have $s\ge r$, so there are at least two
distinct~$w_i$'s in the walk; we have $x_t=w_s$, so $x_t\not=w_i=x_i$ for $0\le
i\le r-1$, so there are at least two distinct~$x_i$'s in the walk; and
$w_r\not=x_r$, so either the walk contains at least three distinct~$w_i$'s or
it contains at least three distinct~$x_i$'s (or both). So $G$ contains a cycle,
which is a contradiction. Therefore, for any two distinct vertices $u,v\in V$,
there exists a unique path in~$G$ between $u$~and~$v$.

\medbreak

\noindent$\rm(a)\implies(c)$.\enspace Suppose $G$ is a tree. Then certainly $G$
is connected. Let $e=\{u,v\}\in E$ be any edge in~$G$. Consider the graph
$H=(V,E\setminus\{e\})$ formed from~$G$ by removing the edge~$e$. If there
exists a path $(u=w_0,w_1,w_2,\ldots,w_{k-1},w_k=v)$ in~$H$ between
$u$~and~$v$, then its length~$k$ must be at least~2 because $\{u,v\}$ is not an
edge in~$H$; so $(u=w_0,w_1,w_2,\ldots,w_{k-1},w_k=v,u)$ is a cycle in~$G$. But
this contradicts the fact that $G$ is acyclic. So there can be no path in~$H$
between $u$~and~$v$, which means that $H$ is disconnected. As the edge $e\in E$
was arbitrary, this shows that $G$ is minimally connected.

\medbreak

\noindent$\rm(a)\implies(d)$.\enspace Suppose $G$ is a tree. Then certainly $G$
is acyclic. If $G$ has no two nonadjacent vertices, then statement~(d) is
vacuously true, and there is nothing more to show, so suppose this is not the
case. Let $u$~and~$v$ be any two nonadjacent vertices in~$G$, and consider the
graph $H=\bigl(V,E\cup\bigl\{\{u,v\}\bigr\}\bigr)$ formed from~$G$ by adding
the edge $\{u,v\}$. Since $G$ is connected, there exists a path
$(u=w_0,w_1,w_2,\ldots,w_{k-1},w_k=v)$ in~$G$ between $u$~and~$v$, and $k\ge2$
because $u$~and~$v$ are not adjacent in~$G$. So
$(u=w_0,w_1,w_2,\ldots,w_{k-1},w_k=v,u)$ is a cycle in~$H$. As $u$~and~$v$ were
arbitrary nonadjacent vertices in~$G$, this shows that $G$ is maximally
acyclic.

\medbreak

\noindent$\rm(a)\implies(e)$.\enspace Suppose $G$ is a tree. Then certainly $G$
is connected. Hence $G$ has exactly one connected component and is acyclic, so
by the vertices--edges--components lemma $G$~must have $n-1$ edges.

\medbreak

\noindent$\rm(a)\implies(f)$.\enspace Suppose $G$ is a tree. Then certainly $G$
is acyclic. And $G$ has exactly one connected component because it is
connected, so by the vertices--edges--components lemma $G$~must have $n-1$
edges.

\medbreak

The following lemma is used many times to prove the implications in which
statement~(b) is the hypothesis.

\proclaim Lemma. {\rm[Unique paths imply acyclicity.]}\enspace If $G=(V,E)$ is
a simple undirected graph such that for any two distinct vertices $u,v\in V$
there exists a unique path in~$G$ between $u$~and~$v$, then $G$ is acyclic.

\noindent{\bf Proof.}\enspace Suppose for the sake of contradiction that $G$
contains a cycle $(v_0,v_1,v_2,\ldots,\allowbreak v_{k-1},\allowbreak v_k=v_0)$,
where $k\ge3$. Then there are two distinct paths $(v_0,v_1,v_2,\ldots,v_{k-1})$
and $({v_0=v_k},v_{k-1})$ between $v_0$~and~$v_{k-1}$, which is a contradiction.
So $G$ is acyclic. \subqed

\medbreak

\noindent$\rm(b)\implies(a)$.\enspace Suppose that for any two distinct
vertices $u,v\in V$ there exists a unique path in~$G$ between $u$~and~$v$. Then
$G$ is connected, and by the preceding lemma $G$~is also acyclic.

\medbreak

\noindent$\rm(b)\implies(c)$.\enspace Suppose that for any two distinct
vertices $u,v\in V$ there exists a unique path in~$G$ between $u$~and~$v$. Then
$G$ is connected. Suppose an edge $e=\{u,v\}\in E$ is removed from~$G$ to form
the graph $H=(V,E\setminus\{e\})$. In~$G$, $(u,v)$~was the unique path between
$u$~and~$v$; this path does not exist in~$H$. Any path in~$H$ is also a path
in~$G$, so in~$H$ there can be no path between $u$~and~$v$, so $H$ is not
connected. As the edge $e\in E$ was arbitrary, this shows that the removal of
any edge from~$G$ produces a disconnected graph. So $G$ is minimally connected.

\medbreak

\noindent$\rm(b)\implies(d)$.\enspace Suppose that for any two distinct
vertices $u,v\in V$ there exists a unique path in~$G$ between $u$~and~$v$. By
the preceding lemma, $G$~is acyclic. If $G$ has no two nonadjacent vertices,
then statement~(d) is vacuously true, and there is nothing more to show, so
suppose this is not the case. Let $u$~and~$v$ be any two nonadjacent vertices
in~$G$, and consider the graph $H=\bigl(V,E\cup\bigl\{\{u,v\}\bigr\}\bigr)$
formed from~$G$ by adding the edge~$\{u,v\}$. By assumption, there exists a
unique path $(u=w_0,w_1,w_2,\ldots,w_{k-1},w_k=v)$ in~$G$ between $u$~and~$v$,
and the length~$k$ of this path must be at least~2 because $\{u,v\}$ is not an
edge in~$G$. So $(u=w_0,w_1,w_2,\ldots,w_{k-1},w_k=v,u)$ is a cycle in~$H$. As
$u$~and~$v$ were arbitrary nonadjacent vertices in~$G$, this shows that $G$ is
maximally acyclic.

\medbreak

\noindent$\rm(b)\implies(e)$.\enspace Suppose that for any two distinct
vertices $u,v\in V$ there exists a unique path in~$G$ between $u$~and~$v$. Then
$G$ is connected, i.e., it has exactly one connected component. By the
preceding lemma, $G$~is acyclic, so by the vertices--edges--components lemma it
must have $n-1$ edges.

\medbreak

\noindent$\rm(b)\implies(f)$.\enspace Exactly the same proof as for
$\rm(b)\implies(e)$.

\medbreak

A similar lemma is useful to prove the implications in which statement~(c) is
the hypothesis.

\proclaim Lemma. {\rm[Minimal connectivity implies acyclicity.]}\enspace If
$G=(V,E)$ is a simple undirected minimally connected graph, then $G$ is
acyclic.

\noindent{\bf Proof.}\enspace Suppose for the sake of contradiction that $G$
has a cycle $(v_0,v_1,v_2,\ldots,v_{k-1},\allowbreak{v_k=v_0})$ of length~$k$,
where $k\ge3$. Let $e$ be the edge $\{v_0,v_1\}$, and consider the graph
$H=(V,E\setminus\{e\})$ formed from~$G$ by removing the edge~$e$. We claim that
$H$ is still connected: Let $u,v\in V$ be distinct vertices. Since $G$ is
connected, there exists a path
$P=({u=w_0},\allowbreak w_1,w_2,\ldots,w_{p-1},w_p=v)$ of length~$p$ in~$G$
between $u$~and~$v$. If $P$ does not use the edge $\{v_0,v_1\}$, then it is
still a path in~$H$. Otherwise, let $q\ge0$ be the least nonnegative integer
such that $w_q\in\{v_0,v_1,v_2\ldots,v_{k-1}\}$, and let $r\le p$ be the
greatest integer no more than~$p$ such that
$w_r\in\{v_0,v_1,v_2,\ldots,v_{k-1}\}$. We must have $q<r$, because $P$
contains both $v_0$~and~$v_1$. Say $w_q=v_s$ and $w_r=v_t$, for some $0\le s<k$
and $0\le t<k$. We must have $s\not=t$ because $q\not=r$ and the path~$P$
contains no repeated vertices. Without loss of generality, assume that $s<t$.
If $s\not=0$, then
$$(u=w_0,w_1,\ldots,w_{q-1},w_q=v_s,v_{s+1},\ldots,v_{t-1},v_t=w_r,w_{r+1},
	\ldots,w_{p-1},w_p=v)$$
is a path in~$H$ between $u$~and~$v$. Otherwise, $s=0$, and
$$(u=w_0,w_1,\ldots,w_{q-1},w_q=v_s=v_0=v_k,v_{k-1},\ldots,v_{t+1},v_t=w_r,
	w_{r+1},\ldots,w_{p-1},w_p=v)$$
is a path in~$H$ between $u$~and~$v$. As $u$~and~$v$ were arbitrary vertices,
this shows that $H$ is connected. Therefore, $G$~is not minimally connected,
which is a contradiction. So $G$ cannot have a cycle, which means that it is
acyclic. \subqed

\medbreak

\noindent$\rm(c)\implies(a)$.\enspace Suppose $G$ is minimally connected. Then
certainly $G$ is connected. By the preceding lemma, $G$~is also acyclic, and
hence a tree.

\medbreak

\noindent$\rm(c)\implies(d)$.\enspace Suppose $G$ is minimally connected. Then
it is connected, so it has exactly one connected component, and by the
preceding lemma it is acyclic. By the vertices--edges--components lemma, then,
$G$~has $n-1$ edges. If an edge is added joining nonadjacent vertices of~$G$,
then the resulting graph~$H$ must still be connected (because adding an edge
cannot disconnect a graph), and $H$ has $n$~edges, so by the
vertices--edges--components lemma it cannot be acyclic. Therefore $G$~is
maximally acyclic.

\medbreak

\noindent$\rm(c)\implies(e)$.\enspace Suppose $G$ is minimally connected. Then
it is connected, so it has exactly one connected component, and by the
preceding lemma it is acyclic. By the vertices--edges--components lemma, then,
$G$~has $n-1$ edges.

\medbreak

\noindent$\rm(c)\implies(f)$.\enspace Exactly the same proof as for
$\rm(c)\implies(e)$.

\medbreak

The next lemma is useful when proving the implications in which statement~(d)
is the hypothesis.

\proclaim Lemma. {\rm[Maximal acyclicity implies connectivity.]}\enspace If
$G=(V,E)$ is a simple undirected maximally acyclic graph, then $G$ is
connected.

\noindent{\bf Proof.}\enspace Let $u,v\in V$ be two distinct vertices in~$G$.
If $u$~and~$v$ are adjacent, then $(u,v)$ is a path in~$G$ from $u$ to~$v$.
Otherwise, because $G$ is maximally acyclic, adding the edge $e=\{u,v\}$ to~$G$
produces the graph $H=(V,E\cup\{e\})$ and $H$~has a cycle
$(w_0,w_1,w_2,\ldots,\allowbreak w_{k-1},\allowbreak{w_k=w_0})$. This cycle
must include the edge~$e$, for otherwise it would be a cycle in~$G$, but $G$ is
acyclic. Without loss of generality, we may assume that $w_0=u$ and $w_1=v$.
Then $(u=w_0=w_k,w_{k-1},w_{k-2},\ldots,w_2,w_1=v)$ is a path from $u$ to~$v$
in~$G$. As $u$~and~$v$ were arbitrary vertices in~$G$, this shows that every
two distinct vertices in~$G$ have a path between them, which is to say, $G$~is
connected. \subqed

\medbreak

\noindent$\rm(d)\implies(a)$.\enspace Suppose $G$ is maximally acyclic. Then
certainly $G$ is acyclic. By the preceding lemma, $G$~is also connected, and
hence a tree.

\medbreak

\noindent$\rm(d)\implies(e)$.\enspace Suppose $G$ is maximally acyclic. Then
certainly $G$ is acyclic, and by the preceding lemma, $G$~is connected, i.e.,
it has exactly one connected component. Therefore, by the
vertices--edges--components lemma, $G$~has $n-1$ edges.

\medbreak

\noindent$\rm(d)\implies(f)$.\enspace Exactly the same proof as for
$\rm(d)\implies(e)$.

\medbreak

\noindent$\rm(e)\implies(a)$.\enspace Suppose $G$ is connected and has $m=n-1$
edges. Then $G$ has exactly one connected component, and $1=n-m$, so by the
vertices--edges--components lemma, $G$~must be acyclic.

\medbreak

\noindent$\rm(e)\implies(c)$.\enspace Suppose $G$ is connected and has $n-1$
edges. If any edge is removed from~$G$, then the resulting graph~$H$ has $n-2$
edges, so by the vertices--edges--components lemma $H$~has at least two
connected components, which is to say, $H$~is disconnected. Therefore $G$ is
minimally connected.

\medbreak

\noindent$\rm(e)\implies(d)$.\enspace Suppose $G$ is connected and has $m=n-1$
edges. Then $G$ has exactly one connected component, and $1=n-m$, so by the
vertices--edges--components lemma, $G$~must be acyclic. If any edge is added
joining nonadjacent vertices of~$G$, then the resulting graph~$H$ is still
connected (because adding an edge cannot disconnect a graph), so $H$ still has
exactly one connected component, but $H$~has $n$~edges, so by the
vertices--edges--components lemma, $H$~cannot be acyclic. Therefore $G$ is
maximally acyclic.

\medbreak

\noindent$\rm(e)\implies(f)$.\enspace Exactly the same proof as for
$\rm(e)\implies(a)$.

\medbreak

\noindent$\rm(f)\implies(a)$.\enspace Suppose $G$ is acyclic and has $n-1$
edges. By the vertices--edges--components lemma, $G$~has exactly one connected
component, i.e., $G$~is connected.

\medbreak

\noindent$\rm(f)\implies(c)$.\enspace Suppose $G$ is acyclic and has $n-1$
edges. By the vertices--edges--components lemma, $G$~has exactly one connected
component, i.e., $G$~is connected. If any edge is removed from~$G$, then the
resulting graph~$H$ has $n-2$ edges, so by the vertices--edges--components
lemma $H$~has at least two connected components, which is to say, $H$~is
disconnected. Therefore $G$ is minimally connected.

\medbreak

\noindent$\rm(f)\implies(d)$.\enspace Suppose $G$ is acyclic and has $n-1$
edges. If any edge is added joining nonadjacent vertices of~$G$, then the
resulting graph~$H$ will have $n$~edges. If $H$ is acyclic, then by the
vertices--edges--components lemma it has zero connected components, which is
impossible. Thus $H$ has a cycle, and therefore $G$ is maximally acyclic.

\medbreak

\noindent$\rm(f)\implies(e)$.\enspace Exactly the same proof as for
$\rm(f)\implies(a)$. \qed

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bye
