\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage{amsfonts}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage{ifthen}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{tikz}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Tuesday, May 15, 2018 23:21:22}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newcounter{exer}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fns}{\begin{footnotesize}}{\end{footnotesize}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\id}{\operatorname{id}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\conncomp}{\operatorname{conncomp}}
\newcommand{\conn}{\operatorname{conn}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\are}{\ar@{-}}
\newcommand{\arebi}[1][]{\ar@{<-}@/_/[#1] \ar@/^/[#1]}
\newcommand\staircasepath[4]{
\fill[cyan!25]  (#1) rectangle +(#2,#3);
\fill[fill=lime]
(#1)
\foreach \dir in {#4}{
\ifnum\dir=1
-- ++(1,0)
\else
-- ++(0,1)
\fi
} |- (#1);
\draw[help lines] (#1) grid +(#2,#3);
\draw[dashed] (#1) -- +(#2,#2);
\coordinate (prev) at (#1);
\foreach \dir in {#4}{
\ifnum\dir=1
\coordinate (dep) at (1,0);
\else
\coordinate (dep) at (0,1);
\fi
\draw[line width=2pt,-stealth] (prev) -- ++(dep) coordinate (prev);
};
}
\newcommand\delannoypath[4]{
\fill[cyan!25]  (#1) rectangle +(#2,#3);
\fill[fill=lime]
(#1)
\foreach \dir in {#4}{
\ifnum\dir=1
-- ++(1,0)
\else
	  \ifnum\dir=0
-- ++(0,1)
	  \else
	  -- ++(1,1)
	  \fi
\fi
} |- (#1);
\draw[help lines] (#1) grid +(#2,#3);
\coordinate (prev) at (#1);
\foreach \dir in {#4}{
\ifnum\dir=1
\coordinate (dep) at (1,0);
\else
	  \ifnum\dir=0
\coordinate (dep) at (0,1);
	  \else
	  \coordinate (dep) at (1,1);
	  \fi
\fi
\draw[line width=2pt,-stealth] (prev) -- ++(dep) coordinate (prev);
};
}
\newcommand\dyckpath[3]{
\fill[fill=lime]
(#1)
\foreach \dir in {#3}{
\ifnum\dir=1
-- ++(1,-1)
\else
-- ++(1,1)
\fi
} |- (#1);
\draw[help lines] (#1) grid +(2*#2, #2);
\coordinate (prev) at (#1);
\foreach \dir in {#3}{
\ifnum\dir=1
\coordinate (dep) at (1,-1);
\else
\coordinate (dep) at (1,1);
\fi
\draw[line width=2pt,-stealth] (prev) -- ++(dep) coordinate (prev);
};
}
\ihead{Math 4707 Spring 2018 (Darij Grinberg): midterm 3}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 4707 Spring 2018 (Darij Grinberg): midterm 3 with solutions
[preliminary version]}
\end{center}

%

%TCIMACRO{\TeXButton{tableofcontents}{\tableofcontents}}%
%BeginExpansion
\tableofcontents
%EndExpansion


\bigskip

Recall the following:

\begin{itemize}
\item If $n\in\mathbb{N}$, then $\left[  n\right]  $ denotes the $n$-element
set $\left\{  1,2,\ldots,n\right\}  $.
\end{itemize}

\subsection{Ordering acyclic digraphs}

See \href{http://www.cip.ifi.lmu.de/~grinberg/t/17s/hw2s.pdf}{Spring
2017 Math 5707 Homework set \#2} (or
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/4707-2018apr23.pdf}{our
class notes from April 23}) for the definition of a \textquotedblleft
multidigraph\textquotedblright. We will refer to multidigraphs simply as
\textit{digraphs}. Thus, any digraph $D$ is a triple $\left(  V,A,\varphi
\right)  $, where $V$ and $A$ are finite sets, and where $\varphi$ is a map
$A\rightarrow V\times V$.

\begin{definition}
A digraph is said to be \textit{acyclic} if it has no cycles.
\end{definition}

For example, the digraph%
\begin{equation}%
%TCIMACRO{\TeXButton{an acyclic digraph}{\xymatrix{
%1 \ar[r]^{\alpha} \ar[d]_{\beta} & 2 \ar[d]^{\gamma} \\
%3 \ar@/^/[r]^{\lambda} \ar@/_/[r]_{\mu} & 4
%}} }%
%BeginExpansion
\xymatrix{
1 \ar[r]^{\alpha} \ar[d]_{\beta} & 2 \ar[d]^{\gamma} \\
3 \ar@/^/[r]^{\lambda} \ar@/_/[r]_{\mu} & 4
}
%EndExpansion
\label{ex.dag.order.ex1}%
\end{equation}
is acyclic, whereas the digraph%
\[%
%TCIMACRO{\TeXButton{a non-acyclic digraph}{\xymatrix{
%1 \ar[r]^{\alpha} & 2 \ar[d]^{\gamma} \\
%3 \ar[u]^{\beta} \ar@/^/[r]^{\lambda} & 4 \ar@/^/[l]^{\mu}
%}}}%
%BeginExpansion
\xymatrix{
1 \ar[r]^{\alpha} & 2 \ar[d]^{\gamma} \\
3 \ar[u]^{\beta} \ar@/^/[r]^{\lambda} & 4 \ar@/^/[l]^{\mu}
}%
%EndExpansion
\]
is not acyclic (both $\left(  1,\alpha,2,\gamma,4,\mu,3,\beta,1\right)  $ and
$\left(  3,\lambda,4,\mu,3\right)  $ are cycles of this latter digraph).

[Acyclic digraphs are often called \textquotedblleft dags\textquotedblright,
apparently because the proper abbreviation \textquotedblleft
adgs\textquotedblright\ would be harder to pronounce.]

\begin{exercise}
\label{exe.digraph.acyclic.ts}Let $D=\left(  V,A,\varphi\right)  $ be an
acyclic digraph. Prove that there is a list $\left(  v_{1},v_{2},\ldots
,v_{n}\right)  $ of elements of $V$ such that

\begin{itemize}
\item each element of $V$ appears exactly once in this list $\left(
v_{1},v_{2},\ldots,v_{n}\right)  $;

\item whenever $i$ and $j$ are two elements of $\left[  n\right]  $ such that
some arc of $D$ has source $v_{i}$ and target $v_{j}$, we must have $i<j$.
\end{itemize}

(In other words, prove that there is a list consisting of all vertices of $V$,
which contains each of them exactly once, and with the property that the
source of any arc must appear before the target of this arc in the list. For
example, if $D$ is the digraph (\ref{ex.dag.order.ex1}), then there are two
such lists: $\left(  1,2,3,4\right)  $ and $\left(  1,3,2,4\right)  $.)
\end{exercise}

Exercise \ref{exe.digraph.acyclic.ts} is a fundamental result of far-reaching
use. In the situation of Exercise \ref{exe.digraph.acyclic.ts}, a list
$\left(  v_{1},v_{2},\ldots,v_{n}\right)  $ of elements of $V$ satisfying the
two required conditions is called a
\textit{\href{https://en.wikipedia.org/wiki/Topological_sorting}{\textit{topological
ordering} or \textit{topological sorting}}} of $D$. Any Linux distribution
comes with \href{https://en.wikipedia.org/wiki/Tsort}{a built-in utility for
computing a topological sorting of a digraph, \texttt{tsort}}. For example, if
I want to compute a topological sorting of the digraph%
\begin{equation}%
%TCIMACRO{\TeXButton{a multidigraph}{\xymatrix{
%4 \ar@/^/[r] \ar@/_/[r] \ar[d] & 3 \ar[d] \ar[r] & 5 \\
%6 \ar@/_/[ru] & 1 \ar[r] & 2 \ar[u]
%}} }%
%BeginExpansion
\xymatrix{
4 \ar@/^/[r] \ar@/_/[r] \ar[d] & 3 \ar[d] \ar[r] & 5 \\
6 \ar@/_/[ru] & 1 \ar[r] & 2 \ar[u]
}
%EndExpansion
\label{ex.dag.tsort.ex1}%
\end{equation}
(whose arcs I have not labeled because the names of the arcs don't matter), I
just create a text file (say, \texttt{arcs.txt}) that lists its arcs (each arc
on a separate line, in the format \textquotedblleft\texttt{source
target}\textquotedblright):
\begin{verbatim}
4 3
4 3
3 5
4 6
6 3
3 1
1 2
2 5
\end{verbatim}

and then run \textquotedblleft\texttt{tsort arcs.txt}\textquotedblright, which
yields the following output:
\begin{verbatim}
$ tsort arcs.txt
4
6
3
1
2
5
\end{verbatim}

This is telling me that $\left(  4,6,3,1,2,5\right)  $ is a topological
ordering of the digraph (\ref{ex.dag.tsort.ex1}). And indeed, it is.

Why would Linux provide such a utility? The specific reasons seem to be
historical, but the algorithm itself is highly useful. For example, you want
to install a piece of software through a package manager (e.g.,
\texttt{apt-get install}), but that software depends on some other software
that is not installed, and that latter software in turn depends on some
further software... These dependencies are known (each program declares a list
of other programs it depends on, or at least its direct dependencies), so the
package manager learns a hopefully acyclic digraph whose vertices are software
packages and whose arcs stand for dependencies (i.e., an arc with source $s$
and target $t$ means that program $s$ needs to be installed before $t$). Now
the package manager needs to know in what order the packages may be installed.
That order has to be a topological sorting of the digraph.

I shall outline one of many possible solutions for Exercise
\ref{exe.digraph.acyclic.ts}:

\begin{proof}
[Solution to Exercise \ref{exe.digraph.acyclic.ts} (sketched).]For each vertex
$v$ of $D$, we let $\operatorname*{Anc}\left(  v\right)  $ be the set of all
$w\in V$ such that there exists a path from $w$ to $v$ in $D$. The elements of
$\operatorname*{Anc}\left(  v\right)  $ are called the \textit{ancestors} of
$v$ (whence the notation $\operatorname*{Anc}$).

Now, let $\left(  v_{1},v_{2},\ldots,v_{n}\right)  $ be a list of all vertices
of $D$ in the order of increasing $\left\vert \operatorname*{Anc}\left(
v\right)  \right\vert $, where ties are resolved arbitrarily. In other words,
let $\left(  v_{1},v_{2},\ldots,v_{n}\right)  $ be a list of all vertices of
$D$ (with each vertex appearing exactly once in this list) satisfying%
\begin{equation}
\left\vert \operatorname*{Anc}\left(  v_{1}\right)  \right\vert \leq\left\vert
\operatorname*{Anc}\left(  v_{2}\right)  \right\vert \leq\cdots\leq\left\vert
\operatorname*{Anc}\left(  v_{n}\right)  \right\vert .
\label{sol.digraph.acyclic.ts.1st.ineq}%
\end{equation}
(Such a list clearly exists.)

The digraph $D$ is acyclic, and thus has no cycles.

Now, we claim the following:

\begin{statement}
\textit{Claim 1:} Each element of $V$ appears exactly once in this list
$\left(  v_{1},v_{2},\ldots,v_{n}\right)  $.
\end{statement}

\begin{statement}
\textit{Claim 2:} Whenever $i$ and $j$ are two elements of $\left[  n\right]
$ such that some arc of $D$ has source $v_{i}$ and target $v_{j}$, we must
have $i<j$.
\end{statement}

Once these two claims are proven, the exercise will clearly follow, since the
very assertion of the exercise was the existence of a list $\left(
v_{1},v_{2},\ldots,v_{n}\right)  $ of elements of $V$ satisfying Claim 1 and
Claim 2. So it remains to prove Claim 1 and Claim 2.

[\textit{Proof of Claim 1:} Claim 1 is obvious from the construction of the
list $\left(  v_{1},v_{2},\ldots,v_{n}\right)  $.]

[\textit{Proof of Claim 2:} Let $i$ and $j$ be two elements of $\left[
n\right]  $ such that some arc of $D$ has source $v_{i}$ and target $v_{j}$.
We must prove that $i<j$.

Assume the contrary. Thus, $i\geq j$, so that $j\leq i$. Hence, from
(\ref{sol.digraph.acyclic.ts.1st.ineq}), we obtain $\left\vert
\operatorname*{Anc}\left(  v_{j}\right)  \right\vert \leq\left\vert
\operatorname*{Anc}\left(  v_{i}\right)  \right\vert $.

We know that some arc of $D$ has source $v_{i}$ and target $v_{j}$. Consider
such an arc, and denote it by $a$.

But $\operatorname*{Anc}\left(  v_{i}\right)  \subseteq\operatorname*{Anc}%
\left(  v_{j}\right)  $\ \ \ \ \footnote{\textit{Proof.} Let $t\in
\operatorname*{Anc}\left(  v_{i}\right)  $. Thus, $t$ is an element of $V$
such that there exists a path from $t$ to $v_{i}$ in $D$ (by the definition of
$\operatorname*{Anc}\left(  v_{i}\right)  $). Consider this path; denote it by
$\mathbf{p}$. Extend this path $\mathbf{p}$ further by the arc $a$ and the
vertex $v_{j}$; it then becomes a walk from $t$ to $v_{j}$. Hence, there
exists a walk from $t$ to $v_{j}$. Thus, there exists a path from $t$ to
$v_{j}$ as well (since we can turn any walk into a path by removing redundant
parts). Hence, $t$ is an element of $V$ such that there exists a path from $t$
to $v_{j}$ in $D$. In other words, $t\in\operatorname*{Anc}\left(
v_{j}\right)  $ (by the definition of $\operatorname*{Anc}\left(
v_{j}\right)  $).
\par
Now, forget that we fixed $t$. We thus have proven that $t\in
\operatorname*{Anc}\left(  v_{j}\right)  $ for each $t\in\operatorname*{Anc}%
\left(  v_{i}\right)  $. In other words, $\operatorname*{Anc}\left(
v_{i}\right)  \subseteq\operatorname*{Anc}\left(  v_{j}\right)  $.}. However,
$v_{j}\in\operatorname*{Anc}\left(  v_{j}\right)  $%
\ \ \ \ \footnote{\textit{Proof.} There exists a path from $v_{j}$ to $v_{j}$
in $D$ (namely, the trivial path $\left(  v_{j}\right)  $). Hence, $v_{j}$ is
an element $w$ of $V$ such that there exists a path from $w$ to $v_{j}$ in
$D$. In other words, $v_{j}\in\operatorname*{Anc}\left(  v_{j}\right)  $ (by
the definition of $\operatorname*{Anc}\left(  v_{j}\right)  $).} and therefore
$\operatorname*{Anc}\left(  v_{i}\right)  \neq\operatorname*{Anc}\left(
v_{j}\right)  $\ \ \ \ \footnote{\textit{Proof.} Assume the contrary. Thus,
$\operatorname*{Anc}\left(  v_{i}\right)  =\operatorname*{Anc}\left(
v_{j}\right)  $. Hence, $v_{j}\in\operatorname*{Anc}\left(  v_{j}\right)
=\operatorname*{Anc}\left(  v_{i}\right)  $. In other words, $v_{j}$ is an
element $w$ of $V$ such that there exists a path from $w$ to $v_{i}$ in $D$
(by the definition of $\operatorname*{Anc}\left(  v_{i}\right)  $). In other
words, $v_{j}$ is an element of $V$, and there exists a path from $v_{j}$ to
$v_{i}$ in $D$. Consider this path. Extend this path by the arc $a$ and the
vertex $v_{j}$. The result will be a cycle from $v_{j}$ to $v_{j}$. Thus, the
digraph $D$ has a cycle. This contradicts the fact that the digraph $D$ has no
cycles. This contradiction shows that our assumption was false, qed.}.
Combining this with $\operatorname*{Anc}\left(  v_{i}\right)  \subseteq
\operatorname*{Anc}\left(  v_{j}\right)  $, we conclude that
$\operatorname*{Anc}\left(  v_{i}\right)  $ is a \textbf{proper} subset of
$\operatorname*{Anc}\left(  v_{j}\right)  $. Hence, $\left\vert
\operatorname*{Anc}\left(  v_{i}\right)  \right\vert <\left\vert
\operatorname*{Anc}\left(  v_{j}\right)  \right\vert $. This contradicts
$\left\vert \operatorname*{Anc}\left(  v_{j}\right)  \right\vert
\leq\left\vert \operatorname*{Anc}\left(  v_{i}\right)  \right\vert $. This
contradiction shows that our assumption was false. Thus, we have $i<j$. This
proves Claim 2.]

Having proven both Claim 1 and Claim 2, we are done solving Exercise
\ref{exe.digraph.acyclic.ts} (as explained above).
\end{proof}

\begin{noncompile}
\begin{proof}
[Second solution to Exercise \ref{exe.digraph.acyclic.ts} (incomplete).]In the
following, a $V$\textit{-listing} will mean any list $\left(  w_{1}%
,w_{2},\ldots,w_{n}\right)  $ of all vertices of $D$ that contains each
element of $V$ exactly once. Clearly, there exists at least one $V$-listing
(in fact, there are exactly $\left\vert V\right\vert !$ of them).

We define a binary relation $\prec$ on the set $V$ as follows: For two
elements $u$ and $v$ of $V$, we write $u\prec v$ if there exists a path from
$u$ to $v$ in $D$ of nonzero length. For example, in the digraph
(\ref{ex.dag.order.ex1}), we have $1\prec2$ but also $1\prec4$ (but not
$4\prec2$).

We claim that the relation $\prec$ is asymmetric; this means that if $u$ and
$v$ are two elements of $V$ satisfying $u\prec v$, then%
\begin{equation}
\text{we don't have }v\prec u. \label{sol.digraph.acyclic.ts.asy}%
\end{equation}


[\textit{Proof of (\ref{sol.digraph.acyclic.ts.asy}):} Let $u$ and $v$ be two
elements of $V$ satisfying $u\prec v$. We must prove
(\ref{sol.digraph.acyclic.ts.asy}).

Assume the contrary. Thus, $v\prec u$. By the definition of the relation
$\prec$, this means that there exists a path $\mathbf{p}$ from $v$ to $u$ in
$D$ of nonzero length. Consider such a path $\mathbf{p}$. Likewise, $u\prec v$
shows that there exists a path $\mathbf{q}$ from $u$ to $v$ in $D$ of nonzero
length. Consider such a path $\mathbf{q}$. Concatenating $\mathbf{p}$ with
$\mathbf{q}$ yields a circuit from $v$ to $v$ in $D$, and this circuit has
nonzero length. But every circuit of nonzero length contains a
cycle\footnote{There are various ways to see this: For example, if $\left(
v_{0},a_{1},v_{1},a_{2},v_{2},\ldots,a_{m},v_{m}\right)  $ is a circuit of
nonzero length, then there is a pair $\left(  i,j\right)  $ of two elements
$i$ and $j$ of $\left\{  0,1,\ldots,m\right\}  $ satisfying $i<j$ and
$v_{i}=v_{j}$ (indeed, $\left(  i,j\right)  =\left(  0,m\right)  $ always
works); now, if we take such a pair $\left(  i,j\right)  $ with
\textbf{minimum }$j-i$, then it is easy to see that $\left(  v_{i}%
,a_{i+1},v_{i+1},a_{i+2},v_{i+2},\ldots,a_{j},v_{j}\right)  $ is a cycle of
$D$.}. Hence, we have found a cycle. This contradicts the fact that $D$ has no
cycles (since $D$ is acyclic). This contradiction shows that our assumption
was wrong. This proves (\ref{sol.digraph.acyclic.ts.asy}).]

Now, if $\mathbf{w}=\left(  w_{1},w_{2},\ldots,w_{n}\right)  $ is any
$V$-listing, then we define the \textit{inversions} of $\mathbf{w}$ to be the
pairs $\left(  i,j\right)  \in\left[  n\right]  ^{2}$ satisfying $i<j$ and
$w_{j}\prec w_{i}$.

Not sure if this solution can be salvaged :(
\end{proof}
\end{noncompile}

\subsection{Watersheds in digraphs}

A \textit{simple digraph} means a pair $\left(  V,A\right)  $, where $V$ is a
finite set, and where $A$ is a subset of $V\times V$. We identify every simple
digraph $\left(  V,A\right)  $ with the multidigraph $\left(  V,A,\iota
\right)  $, where $\iota$ is the map sending each $\left(  u,v\right)  \in A$
to $\left(  u,v\right)  \in V\times V$. Thus, simple digraphs are the same as
multidigraphs whose arcs are already pairs of vertices, the first entry being
the source and the second entry being the target. (So the relation between
simple digraphs and multidigraphs is the same as the relation between simple
graphs and multigraphs.)

\Needspace{25cm}

\begin{example}
Consider the following simple digraph:%
\begin{equation}
\xymatrix{ & 1 \ar[dl] \ar[dr] \\ 2 \ar[dd] \ar[dr] & & 4 \ar[dd] \ar[dl] \\ & 3 \ar[dl] \ar[dr] \\ 6 \ar[d] & & 5 \\ 7 }.
\label{eq.exa.confluence.1}%
\end{equation}
Imagine a game chip placed initially at the vertex $1$. The chip is allowed to
move along the arcs of the digraph (from source to target). For example, the
chip can first move along the arc $\left(  1,2\right)  $ to $2$, then along
the arc $\left(  2,3\right)  $ to $3$, then along the arc $\left(  3,5\right)
$ to $5$. Once it arrives at $5$, it can no longer move, because there are no
arcs with source $5$. We say that $5$ is a \textit{sink} for this reason (see
Exercise \ref{exe.confluence.diamond} below for the precise definition).

Alternatively, the chip could have moved along the arc $\left(  1,2\right)  $
to $2$, then along the arc $\left(  2,6\right)  $ to $6$, then along the arc
$\left(  6,7\right)  $ to $7$. At this point it would again be stuck, since
$7$ is a sink.

Thus, the chip can get stuck in \textbf{two different sinks}, depending on the
path it takes. (It will always get stuck in \textbf{some} sink, because our
digraph has no cycles.)

Now, consider the following simple digraph:%
\begin{equation}
\xymatrix{ 7 \ar[d] \\ 6 \ar[dd] \ar[dr] & & 5 \ar[dd] \ar[dl] & 8 \ar[d] & 10 \ar[dl] \\ & 3 \ar[dr] \ar[dl] & & 9 \\ 2 \ar[dr] & & 4 \ar[dl] \\ & 1 }.
\label{eq.exa.confluence.2}%
\end{equation}
This time, any chip starting at any given vertex will necessarily get stuck at
\textbf{the same sink} no matter what path it takes (either the sink $1$, if
it started at one of the vertices $1,2,3,4,5,6,7$; or the sink $9$, if it
started at one of the vertices $8,9,10$). How can we show this without
checking all possible paths?

One criterion, which is clearly necessary, is that there are no
\textquotedblleft watershed vertices\textquotedblright: i.e., there is no
vertex $u$ from which the chip can take two different arcs $\left(
u,v\right)  $ and $\left(  u,w\right)  $ such that $v$ and $w$
\textquotedblleft never meet again\textquotedblright\ (i.e., there exists no
vertex reachable both from $v$ and from $w$). For example, the digraph
(\ref{eq.exa.confluence.1}) has a \textquotedblleft watershed
vertex\textquotedblright\ (namely, $3$, because the arcs $\left(  3,5\right)
$ and $\left(  3,6\right)  $ lead to the vertices $5$ and $6$ which
\textquotedblleft never meet again\textquotedblright).

The next exercise claims that this condition is also sufficient (as long as
our digraph is acyclic). That is, if there are no \textquotedblleft watershed
vertices\textquotedblright\ and no cycles, then the sink at which a chip gets
stuck is uniquely determined by the vertex it started at (rather than by the
path it took).
\end{example}

\begin{exercise}
\label{exe.confluence.diamond}Let $D$ be an acyclic multidigraph. A vertex $v$
of $D$ is said to be a \textit{sink} if there is no arc of $D$ with source $v$.

If $u$ and $v$ are any two vertices of $D$, then:

\begin{itemize}
\item we write $u\longrightarrow v$ if and only if $D$ has an \textbf{arc}
with source $u$ and target $v$;

\item we write $u\overset{\ast}{\longrightarrow}v$ if and only if $D$ has a
\textbf{path} from $u$ to $v$.
\end{itemize}

The so-called \textit{no-watershed condition} says that for any three vertices
$u$, $v$ and $w$ of $D$ satisfying $u\longrightarrow v$ and $u\longrightarrow
w$, there exists a vertex $t$ of $D$ such that $v\overset{\ast
}{\longrightarrow}t$ and $w\overset{\ast}{\longrightarrow}t$.

Assume that the no-watershed condition holds. Prove that for each vertex $p$
of $D$, there exists \textbf{exactly one} sink $q$ of $D$ such that
$p\overset{\ast}{\longrightarrow}q$.

[\textbf{Hint:} Induction on the \textquotedblleft height\textquotedblright%
\ of $p$ (that is, the length of a longest path starting at $p$).]
\end{exercise}

Exercise \ref{exe.confluence.diamond} is a well-known result rewritten in the
language of digraphs. The result is known as \textit{Newman's diamond lemma},
or, more precisely, its variant where the well-foundedness condition is
replaced by finiteness and acyclicity. Note that the \textquotedblleft
no-watershed condition\textquotedblright\ is commonly called the
\textit{diamond condition} or \textit{local confluence}. My talk
\cite{diamond-talk} gives an introduction into the subject, including an
outline of a solution to Exercise \ref{exe.confluence.diamond}. Other
references are collected in the MathOverflow post \#289300 \cite{MO289300}.
Most authors working in this subject don't use the concept of multidigraphs,
but instead speak of \textquotedblleft abstract rewriting
systems\textquotedblright; the vertices of $D$ are then called the
\textquotedblleft objects\textquotedblright, the relation $\longrightarrow$ is
called the \textquotedblleft reduction relation\textquotedblright, and the
sinks of $D$ are called the \textquotedblleft normal forms\textquotedblright.
The claim of Exercise \ref{exe.confluence.diamond} (and its more general
version, in which $D$ may have infinitely many vertices and arcs, but we
requires the extra condition that there exist no infinite paths $v_{0}%
\longrightarrow v_{1}\longrightarrow v_{2}\longrightarrow\cdots$) is used,
e.g., in the theory of Gr\"{o}bner bases and in the abstract study of
computation (e.g., the Church-Rosser property for $\lambda$-calculus).

\subsection{Arborescences of a wheel}

\begin{definition}
Let $D$ be a digraph, and let $u$ be a vertex of $D$.

\textbf{(a)} Then, $D$ is called a $u$\textit{-arborescence} if and only if
for each vertex $v$ of $D$, there is a \textbf{unique} walk from $u$ to $v$ in
$D$.

\textbf{(b)} Assume that $D$ is a multidigraph $\left(  V,A,\phi\right)  $. A
$u$\textit{-arborescence of }$D$ means a subset $B$ of $A$ such that the
multidigraph $\left(  V,B,\phi\mid_{B}\right)  $ is a $u$-arborescence.
\end{definition}

I believe that what I just called a \textquotedblleft$u$%
-arborescence\textquotedblright\ is the same as what Vic called
\textquotedblleft arborescence with root $u$\textquotedblright, except that
maybe the arcs are pointing in the opposite direction. My notion of a
\textquotedblleft$u$-arborescence\textquotedblright\ is equivalent to what is
called a \textquotedblleft directed tree with root $u$\textquotedblright\ in
\cite{Sahi13}, but the equivalence is not entirely obvious to prove.

For an example, the simple digraph%
\[%
%TCIMACRO{\TeXButton{a 1-arborescence}{\xymatrix{
%1 \ar[r] \ar[d] & 2 \\
%3 \ar[r] \ar[d] & 5 \ar[d] \\
%4 & 6
%}}}%
%BeginExpansion
\xymatrix{
1 \ar[r] \ar[d] & 2 \\
3 \ar[r] \ar[d] & 5 \ar[d] \\
4 & 6
}%
%EndExpansion
\]
is a $1$-arborescence. Thus, the set%
\[
\left\{  \left(  1,2\right)  ,\left(  1,3\right)  ,\left(  3,4\right)
,\left(  3,5\right)  ,\left(  5,6\right)  \right\}
\]
is a $1$-arborescence of the simple digraph%
\[%
%TCIMACRO{\TeXButton{a grid digraph}{\xymatrix{
%1 \ar[r] \ar[d] & 2 \ar[d] \\
%3 \ar[r] \ar[d] & 5 \ar[d] \\
%4 \ar[r] & 6
%}}}%
%BeginExpansion
\xymatrix{
1 \ar[r] \ar[d] & 2 \ar[d] \\
3 \ar[r] \ar[d] & 5 \ar[d] \\
4 \ar[r] & 6
}%
%EndExpansion
.
\]


\begin{lemma}
\label{lem.arborescences.1in}Let $D$ be a digraph. Let $u$ be a vertex of $D$.
Let $B$ be a $u$-arborescence of $D$.

\textbf{(a)} No arc in $B$ has target $u$.

\textbf{(b)} Let $v$ be a vertex of $D$ distinct from $u$. Then, exactly one
arc in $B$ has target $v$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.arborescences.1in} (sketched).]Write the digraph $D$
in the form $D=\left(  V,A,\phi\right)  $. The multidigraph $\left(
V,B,\phi\mid_{B}\right)  $ is a $u$-arborescence (since $B$ is a
$u$-arborescence of $D$). In other words, for each vertex $v\in V$, there is a
\textbf{unique} walk from $u$ to $v$ in $\left(  V,B,\phi\mid_{B}\right)  $.
Let us denote this walk by $\mathbf{w}_{v}$. Of course, $\mathbf{w}_{v}$ is a
walk in the digraph $D$ as well (since $B\subseteq A$).

\textbf{(a)} Assume the contrary. Thus, some arc $b\in B$ has target $u$.
Consider this $b$. Let $v$ be the source of this arc $b$. We can extend the
walk $\mathbf{w}_{v}$ (which is a walk from $u$ to $v$ in $\left(
V,B,\phi\mid_{B}\right)  $) by the arc $b$ (which is an arc from $v$ to $u$ in
$\left(  V,B,\phi\mid_{B}\right)  $) and the vertex $u$. The result is a walk
from $u$ to $u$ in $\left(  V,B,\phi\mid_{B}\right)  $ having nonzero length.
But there also exists a walk from $u$ to $u$ in $\left(  V,B,\phi\mid
_{B}\right)  $ having zero length (namely, the walk $\left(  u\right)  $).
Thus, we have found \textbf{two different} walks from $u$ to $u$ in $\left(
V,B,\phi\mid_{B}\right)  $. This contradicts the fact that there is a
\textbf{unique} walk from $u$ to $u$ in $\left(  V,B,\phi\mid_{B}\right)  $,
namely $\mathbf{w}_{u}$ (because this is how $\mathbf{w}_{u}$ was defined).
This contradiction shows that our assumption was false. Thus, Lemma
\ref{lem.arborescences.1in} \textbf{(a)} is proven.

\textbf{(b)} Recall that $\mathbf{w}_{v}$ is a walk from $u$ to $v$ in
$\left(  V,B,\phi\mid_{B}\right)  $. This walk $\mathbf{w}_{v}$ has at least
one arc (since $v$ is distinct from $u$), and thus has a last arc. Let $b$ be
this last arc. Thus, $b$ is an arc in $B$ that has target $v$. Hence,
\textbf{at least one} arc in $B$ has target $v$. But we must prove that
\textbf{exactly one} arc in $B$ has target $v$. Thus, it remains to prove that
$b$ is the \textbf{only} arc in $B$ that has target $v$.

Indeed, let $c$ be any arc in $B$ that has target $v$. We must prove that
$c=b$.

Let $w$ be the source of the arc $c$. Then, $\mathbf{w}_{w}$ is a walk from
$u$ to $w$ in $\left(  V,B,\phi\mid_{B}\right)  $ (by the definition of
$\mathbf{w}_{w}$). We can extend this walk $\mathbf{w}_{w}$ (which is a walk
from $u$ to $w$ in $\left(  V,B,\phi\mid_{B}\right)  $) by the arc $c$ (which
is an arc from $w$ to $v$ in $\left(  V,B,\phi\mid_{B}\right)  $) and the
vertex $v$. The result is a walk from $u$ to $v$ in $\left(  V,B,\phi\mid
_{B}\right)  $ whose last arc is $c$. This walk must therefore be
$\mathbf{w}_{v}$ (because $\mathbf{w}_{v}$ was defined to be the
\textbf{unique} walk from $u$ to $v$ in $\left(  V,B,\phi\mid_{B}\right)  $).
Hence, $c$ (being the last arc of this walk) must be the last arc of the walk
$\mathbf{w}_{v}$. But we already know that $b$ is the last arc of the walk
$\mathbf{w}_{v}$ (since this is how $b$ was defined). Hence, $c=b$.

Now, forget that we fixed $c$. We thus have shown that if $c$ is any arc in
$B$ that has target $v$, then $c=b$. Thus, $b$ is the \textbf{only} arc in $B$
that has target $v$. As explained, this concludes the proof of Lemma
\ref{lem.arborescences.1in} \textbf{(b)}.
\end{proof}

\begin{lemma}
\label{lem.arborescences.noc}Let $D=\left(  V,A,\phi\right)  $ be a
multidigraph. Let $u$ be a vertex of $D$. Let $B$ be a $u$-arborescence of
$D$. Then, the multidigraph $\left(  V,B,\phi\mid_{B}\right)  $ has no cycles.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.arborescences.noc} (sketched).]Let $\mathbf{c}$ be a
cycle of the multidigraph $\left(  V,B,\phi\mid_{B}\right)  $. We must derive
a contradiction.

Let $v$ be the starting point of $\mathbf{c}$. The multidigraph $\left(
V,B,\phi\mid_{B}\right)  $ is a $u$-arborescence (since $B$ is a
$u$-arborescence of $D$). Hence, there is a \textbf{unique} walk from $u$ to
$v$ in $\left(  V,B,\phi\mid_{B}\right)  $ (by the definition of a
$u$-arborescence). Let us denote this walk by $\mathbf{w}$. Now, concatenating
this walk $\mathbf{w}$ with the cycle $\mathbf{c}$, we obtain a new walk from
$u$ to $v$ in $\left(  V,B,\phi\mid_{B}\right)  $. This new walk must be
$\mathbf{w}$ (because $\mathbf{w}$ is the \textbf{unique} walk from $u$ to $v$
in $\left(  V,B,\phi\mid_{B}\right)  $). But this contradicts the fact that
this new walk is longer than $\mathbf{w}$ (since it was obtained by
concatenating $\mathbf{w}$ with the cycle $\mathbf{c}$).

Forget that we fixed $\mathbf{c}$.\ We thus have obtained a contradiction for
each cycle $\mathbf{c}$ of the multidigraph $\left(  V,B,\phi\mid_{B}\right)
$. Thus, the multidigraph $\left(  V,B,\phi\mid_{B}\right)  $ has no cycles.
This proves Lemma \ref{lem.arborescences.noc}.
\end{proof}

Notice that Lemma \ref{lem.arborescences.1in} has something like a converse,
which we can use to characterize $u$-arborescences:

\begin{lemma}
\label{lem.arborescences.1in2}Let $D=\left(  V,A,\phi\right)  $ be a
multidigraph. Let $B$ be a subset of $A$. Let $u$ be a vertex of $D$. Assume
the following:

\begin{itemize}
\item No arc in $B$ has target $u$.

\item For each vertex $v$ of $D$ distinct from $u$, there is exactly one arc
in $B$ that has target $v$.

\item For each vertex $v$ of $D$ distinct from $u$, there is at least one walk
from $u$ to $v$ in $\left(  V,B,\phi\mid_{B}\right)  $.
\end{itemize}

Then, $B$ is a $u$-arborescence of $D$.
\end{lemma}

\begin{noncompile}
THE FOLLOWING PROOF HAS NOT BEEN FINISHED!

\begin{proof}
[Proof of Lemma \ref{lem.arborescences.1in2} (sketched).] We define a
$B$\textit{-walk} to mean a walk in the multidigraph $\left(  V,B,\phi\mid
_{B}\right)  $. (Equivalently, a $B$-walk is the same as a walk in the
multidigraph $D$ whose arcs all belong to the set $B$.)

For each vertex $v$ of $B$ distinct from $u$, there is exactly one arc in $B$
that has target $v$. Let us denote this arc by $\alpha_{v}$. Thus, $\alpha
_{v}$ is the unique arc in $B$ that has target $v$. The source of this arc
$\alpha_{v}$ shall be denoted by $\sigma_{v}$.

Our argument will be a organized as a sequence of easy claims.

\begin{statement}
\textit{Claim 1:} For each vertex $v$ of $B$, there is at least one $B$-walk
from $u$ to $v$.
\end{statement}

[\textit{Proof of Claim 1:} We have assumed that for each vertex $v$ of $B$
distinct from $u$, there is at least one walk from $u$ to $v$ in $\left(
V,B,\phi\mid_{B}\right)  $. In other words, for each vertex $v$ of $B$
distinct from $u$, there is at least one $B$-walk from $u$ to $v$. In other
words, Claim 1 holds whenever $v$ is distinct from $u$. It thus only remains
to prove that Claim 1 holds for $v=u$. But this is clear, because there is at
least one $B$-walk from $u$ to $u$ (namely, the trivial walk $\left(
u\right)  $). Thus, Claim 1 is proven.]

\begin{statement}
\textit{Claim 2:} There is exactly one $B$-walk from $u$ to $u$.
\end{statement}

[\textit{Proof of Claim 2:} Let $\mathbf{w}$ be any $B$-walk from $u$ to $u$.
If $\mathbf{w}$ had at least one arc, then $\mathbf{w}$ would have a last arc,
and this last arc would have target $u$; but this would contradict the
assumption that no arc in $B$ has target $u$ (since the last arc of the
$B$-walk $\mathbf{w}$ must be an arc in $B$). Thus, $\mathbf{w}$ has no arcs.
In other words, the walk $\mathbf{w}$ must have the form $\left(  p\right)  $
for some vertex $p\in V$. Consider this $p$. Clearly, $p=u$ (since $\left(
p\right)  =\mathbf{w}$ is a walk from $u$ to $u$). Thus, $\mathbf{w}=\left(
p\right)  =\left(  u\right)  $ (since $p=u$).

Now, forget that we fixed $\mathbf{w}$. We thus have shown that if
$\mathbf{w}$ is any $B$-walk from $u$ to $u$, then $\mathbf{w}=\left(
u\right)  $. Thus, there is only one $B$-walk from $u$ to $u$, namely $\left(
u\right)  $ (since $\left(  u\right)  $ is clearly a $B$-walk from $u$ to
$u$). This proves Claim 2.]

We shall use the following notation: If $x$, $y$ and $z$ are three vertices of
$D$, and if $\mathbf{p}$ is a walk from $x$ to $y$, and if $\mathbf{q}$ is a
walk from $y$ to $z$, then $\mathbf{p}\widehat{}\mathbf{q}$ shall mean the
walk from $x$ to $z$ that is obtained by concatenating the paths $\mathbf{p}$
and $\mathbf{q}$. Explicitly, $\mathbf{p}\widehat{}\mathbf{q}$ is defined by%
\begin{align*}
\mathbf{p}\widehat{}\mathbf{q}  & =\left(  v_{0},a_{1},v_{1},\ldots
,v_{k-1},a_{k},v_{k},b_{1},w_{1},\ldots,b_{\ell},w_{\ell}\right)  \\
& =\left(  v_{0},a_{1},v_{1},\ldots,v_{k-1},a_{k},w_{0},b_{1},w_{1}%
,\ldots,b_{\ell},w_{\ell}\right)
\end{align*}
if $\mathbf{p}$ and $\mathbf{q}$ are written in the forms $\mathbf{p}=\left(
v_{0},a_{1},v_{1},\ldots,v_{k-1},a_{k},v_{k}\right)  $ and $\mathbf{q}=\left(
w_{0},b_{1},w_{1},\ldots,b_{\ell},w_{\ell}\right)  $. Note that the arcs of
$\mathbf{p}\widehat{}\mathbf{q}$ are the arcs of $\mathbf{p}$ and the arcs of
$\mathbf{q}$; thus, if $\mathbf{p}$ and $\mathbf{q}$ are $B$-walks, then
$\mathbf{p}\widehat{}\mathbf{q}$ is a $B$-walk as well.

\begin{statement}
\textit{Claim 3:} Let $v$ be a vertex of $D$ distinct from $u$. Let
$\mathbf{w}$ be any $B$-walk from $u$ to $v$. Then, $\mathbf{w}$ has the form
$\mathbf{w}=\mathbf{p}\widehat{}\left(  \sigma_{v},\alpha_{v},v\right)  $ for
some $B$-walk $\mathbf{p}$ from $u$ to $\sigma_{v}$.
\end{statement}

[\textit{Proof of Claim 3:} We have $v\neq u$ (since $v$ is distinct from
$u$). Thus, the walk $\mathbf{w}$ has at least one
arc\footnote{\textit{Proof.} Assume the contrary. Thus, the walk $\mathbf{w}$
has no arcs. Hence, $\mathbf{w}$ has the form $\left(  p\right)  $ for some
vertex $p\in V$. Thus, $\left(  p\right)  =\mathbf{w}$ is a walk from $u$ to
$v$. Therefore, $u=p$ and $v=p$. Thus, $v=p=u$. This contradicts $v\neq u$.
This contradiction shows that our assumption was wrong, qed.}. Let us write
this walk $\mathbf{w}$ in the form
\[
\mathbf{w}=\left(  w_{0},a_{1},w_{1},a_{2},w_{2},\ldots,w_{k-1},a_{k}%
,w_{k}\right)
\]
for some vertices $w_{0},w_{1},\ldots,w_{k}$ and some arcs $a_{1},a_{2}%
,\ldots,a_{k}$. Since $\mathbf{w}$ is a walk from $u$ to $v$, we thus have
$w_{0}=u$ and $w_{k}=v$. Also, $k\geq1$ (since $\mathbf{w}$ has at least one
arc); thus, the arc $a_{k}$ is well-defined. This arc $a_{k}$ has source
$w_{k-1}$ and target $w_{k}$. Thus, the target of the arc $a_{k}$ is $w_{k}=v$.

But $\mathbf{w}$ is a $B$-walk; thus, its arcs $a_{1},a_{2},\ldots,a_{k}$
belong to $B$. Hence, in particular, $a_{k}\in B$. Thus, $a_{k}$ is an arc in
$B$ that has target $v$ (since the target of $a_{k}$ is $v$). Therefore,
$a_{k}=\alpha_{v}$ (since $\alpha_{v}$ is the unique arc in $B$ that has
target $v$ (by the definition of $\alpha_{v}$)). Now, recall that the arc
$a_{k}$ has source $w_{k-1}$. Hence,%
\begin{align*}
w_{k-1}  & =\left(  \text{the source of }a_{k}\right)  =\left(  \text{the
source of }\alpha_{v}\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }%
a_{k}=\alpha_{v}\right)  \\
& =\sigma_{v}%
\end{align*}
(since $\sigma_{v}$ was defined to be the source of $\alpha_{v}$).

Now, recall that the sequence $\left(  w_{0},a_{1},w_{1},a_{2},w_{2}%
,\ldots,w_{k-1},a_{k},w_{k}\right)  =\mathbf{w}$ is a $B$-walk. Thus, its
subsequence $\left(  w_{0},a_{1},w_{1},a_{2},w_{2},\ldots,w_{k-1}\right)  $ is
a $B$-walk as well. This subsequence is furthermore a $B$-walk from $u$ to
$\sigma_{v}$ (since $w_{0}=u$ and $w_{k-1}=\sigma_{v}$). Denote it by
$\mathbf{q}$. Thus, $\mathbf{q}$ is a $B$-walk from $u$ to $\sigma_{v}$. Also,
$\left(  \sigma_{v},\alpha_{v},v\right)  $ is a walk from $\sigma_{v}$ to $v$.

TO\ BE\ CONTINUED!]

\begin{statement}
\textit{Claim 4:} Let $m\in\mathbb{N}$. Let $v$ be a vertex of $D$ such that
there exists a $B$-walk from $u$ to $v$ of length $m$. Then, there exists
\textbf{exactly one} $B$-walk from $u$ to $v$.
\end{statement}

[\textit{Proof of Claim 4:} We shall prove Claim 4 by induction on $m$:

\textit{Induction base:} Claim 4 holds for $m=0$%
\ \ \ \ \footnote{\textit{Proof.} Assume that $m=0$. Recall that there exists
a $B$-walk from $u$ to $v$ of length $m$. This $B$-walk has length $m$, and
thus has length $0$ (since $m=0$). Hence, this $B$-walk must have the form
$\left(  p\right)  $ for some vertex $p\in V$. Consider this $p$. Thus,
$\left(  p\right)  $ is a $B$-walk from $u$ to $v$. Hence, $p=u$ and $p=v$.
Therefore, $v=p=u$. But Claim 2 shows that there is exactly one $B$-walk from
$u$ to $u$. In other words, there is exactly one $B$-walk from $u$ to $v$
(since $v=u$). Thus, Claim 2 holds. So we have proven Claim 2 under the
assumption that $m=0$.}. This completes the induction base.

\textit{Induction step:} Let $M$ be a positive integer. Assume that Claim 2
holds for $m=M-1$. We must prove that Claim 2 holds for $m=M$.

Let $v$ be a vertex of $D$ such that there exists a $B$-walk from $u$ to $v$
of length $M$. Consider such a $B$-walk, and denote it by $\mathbf{m}$.

We intend to prove that there exists \textbf{exactly one} $B$-walk from $u$ to
$v$. If $v=u$, then this follows from Claim 2. Thus, for the rest of this
proof, we can WLOG assume that we don't have $v=u$. Assume this. Hence, $v\neq
u$.

Now, let $\mathbf{w}$ be \textbf{any} $B$-walk from $u$ to $v$. This walk
$\mathbf{w}$ has at least one arc\footnote{\textit{Proof.} Assume the
contrary. Thus, the walk $\mathbf{w}$ has no arcs. Hence, $\mathbf{w}$ has the
form $\left(  p\right)  $ for some vertex $p\in V$. Thus, $\left(  p\right)
=\mathbf{w}$ is a walk from $u$ to $v$. Therefore, $u=p$ and $v=p$. Thus,
$v=p=u$. This contradicts $v\neq u$. This contradiction shows that our
assumption was wrong, qed.}. Let us write this walk $\mathbf{w}$ in the form
\[
\mathbf{w}=\left(  w_{0},a_{1},w_{1},a_{2},w_{2},\ldots,w_{k-1},a_{k}%
,w_{k}\right)
\]
for some vertices $w_{0},w_{1},\ldots,w_{k}$ and some arcs $a_{1},a_{2}%
,\ldots,a_{k}$. Since $\mathbf{w}$ is a walk from $u$ to $v$, we thus have
$w_{0}=u$ and $w_{k}=v$. Also, $k\geq1$ (since $\mathbf{w}$ has at least one
arc); thus, the arc $a_{k}$ is well-defined. This arc $a_{k}$ has source
$w_{k-1}$ and target $w_{k}$.
\end{proof}

Indeed, assume the contrary. TO BE CONTINUED!
\end{noncompile}

We leave the proof of this lemma to the reader.

Two much less trivial properties of arborescences are the following:

\begin{theorem}
\label{thm.arborescences.harmonic}Let $D=\left(  V,A,\phi\right)  $ be a
multidigraph. For any two vertices $i$ and $j$ of $D$, we let $a_{i,j}$ be the
number of arcs of $D$ having source $i$ and target $j$. For any vertex $i$ of
$D$, we let $w_{i}$ be the number of $i$-arborescences of $D$. Then, each
vertex $i$ of $D$ satisfies%
\[
\sum_{j\in V}a_{i,j}w_{j}=\left(  \sum_{k\in V}a_{k,i}\right)  w_{i}.
\]

\end{theorem}

Theorem \ref{thm.arborescences.harmonic} is essentially \cite[Theorem
1]{Sahi13} (restated without using matrices, and with weighted arcs instead of
parallel arcs: e.g., instead of having $4$ arcs with source $i$ and target
$j$, \cite[Theorem 1]{Sahi13} would speak of an arc of weight $4$ from $i$ to
$j$). Here is the main idea of its proof:

\begin{proof}
[Hint to the proof of Theorem \ref{thm.arborescences.harmonic}.]For any two
vertices $i$ and $j$ of $D$, we let $A_{i,j}$ be the set of all arcs of $D$
having source $i$ and target $j$. Note that this set satisfies $\left\vert
A_{i,j}\right\vert =a_{i,j}$.

For any vertex $i$ of $D$, we let $W_{i}$ be the set of all $i$-arborescences
of $D$. This set $W_{i}$ satisfies $\left\vert W_{i}\right\vert =w_{i}$.

Now, let $i$ be a vertex of $D$. A subset $B$ of $A$ is said to be
\textit{univalent} if for each $v\in V$, there is exactly one arc in $B$ whose
target is $v$. A subset $B$ of $A$ is said to be an $i$\textit{-unicycle} if
it has the following properties:

\begin{itemize}
\item The subset $B$ is univalent.

\item Each cycle of the digraph $\left(  V,B,\phi\mid_{B}\right)  $ contains
the vertex $i$.

\item The digraph $\left(  V,B,\phi\mid_{B}\right)  $ has exactly one cycle
from $i$ to $i$.
\end{itemize}

(Note that these properties imply that the digraph $\left(  V,B,\phi\mid
_{B}\right)  $ has only one cycle, up to cyclic rotation. Therefore the name
\textquotedblleft$i$-unicycle\textquotedblright.)

If $B$ is an $i$-unicycle, then

\begin{itemize}
\item the unique cycle from $i$ to $i$ of the digraph $\left(  V,B,\phi
\mid_{B}\right)  $ will be denoted by $z\left(  B\right)  $;

\item the first arc of this cycle will be denoted by $f\left(  B\right)  $;

\item the last arc of this cycle will be denoted by $\ell\left(  B\right)  $;

\item the target of $f\left(  B\right)  $ will be denoted by $\mathfrak{j}%
\left(  B\right)  $;

\item the source of $\ell\left(  B\right)  $ will be denoted by $\mathfrak{k}%
\left(  B\right)  $.
\end{itemize}

The following facts are important and easy to check:

\begin{statement}
\textit{Claim 1:} Let $v$ be a vertex of $D$. Let $\beta$ be an arc of $D$
with target $v$ such that $i$ is either the source or the target of $v$. Let
$C$ be a $v$-arborescence of $D$. Then, $C\cup\left\{  \beta\right\}  $ is a
$i$-unicycle.
\end{statement}

\begin{statement}
\textit{Claim 2:} Let $B$ be an $i$-unicycle. Let $\beta$ be an arc of the
cycle $z\left(  B\right)  $, and let $v$ be the target of $\beta$. Then,
$B\setminus\left\{  \beta\right\}  $ is a $v$-arborescence of $D$.
\end{statement}

Now, we can prove that the map%
\begin{align*}
\left\{  i\text{-unicycles}\right\}   &  \rightarrow\bigcup_{j\in V}\left(
A_{i,j}\times W_{j}\right)  ,\\
B  &  \mapsto\left(  f\left(  B\right)  ,B\setminus\left\{  f\left(  B\right)
\right\}  \right)
\end{align*}
is well-defined (i.e., most importantly, if $B$ is an $i$-unicycle, then
$B\setminus\left\{  f\left(  B\right)  \right\}  $ is a $\mathfrak{j}\left(
B\right)  $-arborescence of $D$ (by Claim 2)) and bijective (indeed, its
inverse map sends a pair $\left(  \beta,C\right)  \in A_{i,j}\times W_{j}$ for
any $j\in V$ to the $i$-unicycle $C\cup\left\{  \beta\right\}  $ (which is
well-defined by Claim 1)). Thus, it is a bijection from $\left\{
i\text{-unicycles}\right\}  $ to $\bigcup_{j\in V}\left(  A_{i,j}\times
W_{j}\right)  $. Hence,%
\begin{align}
\left\vert \left\{  i\text{-unicycles}\right\}  \right\vert  &  =\left\vert
\bigcup_{j\in V}\left(  A_{i,j}\times W_{j}\right)  \right\vert =\sum_{j\in
V}\underbrace{\left\vert A_{i,j}\right\vert }_{=a_{i,j}}\cdot
\underbrace{\left\vert W_{j}\right\vert }_{=w_{j}}\nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{since the sets }A_{i,j}\times W_{j}\text{ for different }j\in V\\
\text{are disjoint (because the sets }A_{i,j}\text{ for different }j\in V\\
\text{are disjoint)}%
\end{array}
\right) \nonumber\\
&  =\sum_{j\in V}a_{i,j}w_{j}. \label{pf.thm.arborescences.harmonic.LHS}%
\end{align}


On the other hand, we can prove that the map%
\begin{align*}
\left\{  i\text{-unicycles}\right\}   &  \rightarrow\left(  \bigcup_{k\in
V}A_{k,i}\right)  \times W_{i},\\
B  &  \mapsto\left(  \ell\left(  B\right)  ,B\setminus\left\{  \ell\left(
B\right)  \right\}  \right)
\end{align*}
is well-defined (i.e., most importantly, if $B$ is an $i$-unicycle, then
$B\setminus\left\{  \ell\left(  B\right)  \right\}  $ is an $i$-arborescence
of $D$ (by Claim 2)) and bijective (indeed, its inverse map sends a pair
$\left(  \beta,C\right)  \in A_{k,i}\times W_{i}$ for any $k\in V$ to the
$i$-unicycle $C\cup\left\{  \beta\right\}  $ (which is well-defined by Claim
1)). Thus, it is a bijection from $\left\{  i\text{-unicycles}\right\}  $ to
$\left(  \bigcup_{k\in V}A_{k,i}\right)  \times W_{i}$. Hence,%
\begin{align*}
\left\vert \left\{  i\text{-unicycles}\right\}  \right\vert  &  =\left\vert
\left(  \bigcup_{k\in V}A_{k,i}\right)  \times W_{i}\right\vert =\left(
\sum_{k\in V}\underbrace{\left\vert A_{k,i}\right\vert }_{=a_{k,i}}\right)
\cdot\underbrace{\left\vert W_{i}\right\vert }_{=w_{i}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{since the sets }A_{k,i}\text{ for different }k\in V\\
\text{are disjoint}%
\end{array}
\right) \\
&  =\left(  \sum_{k\in V}a_{k,i}\right)  w_{i}.
\end{align*}
Comparing this with (\ref{pf.thm.arborescences.harmonic.LHS}), we obtain
$\sum_{j\in V}a_{i,j}w_{j}=\left(  \sum_{k\in V}a_{k,i}\right)  w_{i}$. This
proves Theorem \ref{thm.arborescences.harmonic}.
\end{proof}

\begin{noncompile}
Alternative proof of Theorem \ref{thm.arborescences.harmonic} (should be a lot
nicer to write up): For each arc $b\in A$ and each $i\in V$, we let $w_{i,b}$
be the number of $i$-arborescences of $D$ that contain the arc $b$. Then, it
suffices to show that if $b$ is an arc from $k$ to $i$, then%
\[
\sum_{j\in V}a_{i,j}w_{j,b}=w_{i}.
\]
This can be proven bijectively using Lemma \ref{lem.arborescences.1in2}
(instead of $i$-unicycles).
\end{noncompile}

\begin{definition}
Let $D=\left(  V,A,\phi\right)  $ be a multidigraph. Let $v$ be a vertex of
$D$.

\textbf{(a)} The \textit{indegree} $\operatorname*{indeg}v$ of $v$ denotes the
number of arcs $a\in A$ having target $v$.

\textbf{(b)} The \textit{outdegree} $\operatorname*{outdeg}v$ of $v$ denotes
the number of arcs $a\in A$ having source $v$.
\end{definition}

\begin{theorem}
\label{thm.arborescences.equal}Let $D$ be a multidigraph. For any vertex $i$
of $D$, we let $w_{i}$ be the number of $i$-arborescences of $D$. Assume that
each vertex $v$ of $D$ satisfies $\operatorname*{indeg}%
v=\operatorname*{outdeg}v$. Then, $w_{i}=w_{j}$ for any two vertices $i$ and
$j$ of $D$.
\end{theorem}

Theorem \ref{thm.arborescences.equal} appears in various sources (e.g.,
\cite[Chapter 11, \S 3, Corollary 1]{Berge91}), and can be derived from the
BEST theorem (see, e.g., \cite[Theorem 2]{Klings11}\footnote{Klingsberg's
\cite[\S 2]{Klings11} gives a self-contained proof of the BEST theorem. If you
want to read it, keep in mind that the condition that $D$ be \textquotedblleft
connected\textquotedblright\ (I am not sure whether he means \textquotedblleft
strongly connected\textquotedblright\ or \textquotedblleft weakly
connected\textquotedblright\ by this word) is never used in the proof and thus
can (and should) be removed from the statement of \cite[Theorem 2]{Klings11}.
Also, keep in mind that he works with \textquotedblleft trees flowing
into\textquotedblright\ a vertex $u$; this is almost the same as
$u$-arborescences, but instead of requiring a unique walk from $u$ to any
vertex $v$, he requires a unique walk from any vertex $v$ to $u$. Thus, of
course, the concept of a tree flowing into $u$ becomes the concept of a
$u$-arborescence once you reverse each arc of your digraph (i.e., swap the
source with the target). Also, Klingsberg defines a circuit to be an
equivalence class of circuits up to cyclic rotation.} or \cite[\S I.3, Theorem
13]{Bollob98}\footnote{When reading Bollob\'{a}s's \cite[\S I.3]{Bollob98},
keep in mind that he works with \textquotedblleft spanning trees oriented
towards\textquotedblright\ a vertex $u$; this is almost the same as
$u$-arborescences, but instead of requiring a unique walk from $u$ to any
vertex $v$, he requires a unique walk from any vertex $v$ to $u$. This is
exactly what Klingsberg calls a \textquotedblleft tree flowing
into\textquotedblright\ $u$. Also, Bollob\'{a}s counts cyclic rotations of a
circuit as identical.} or \cite[Corollary 4.1]{JacGou79}). The main idea is
that if $D$ is a multidigraph with the property that each vertex of $D$
satisfies $\operatorname*{indeg}v=\operatorname*{outdeg}v$, then the BEST
theorem shows that the total number of Eulerian circuits of $D$ (counted up to
cyclic rotation) equals%
\[
w_{i}\cdot\prod_{v\in V}\left(  \operatorname*{outdeg}v-1\right)  !
\]
for any given $i\in V$. Since this number clearly doesn't depend on $i$, we
thus conclude that any two vertices $i$ and $j$ of such a multidigraph $D$
satisfy%
\[
w_{i}\cdot\prod_{v\in V}\left(  \operatorname*{outdeg}v-1\right)  !=w_{j}%
\cdot\prod_{v\in V}\left(  \operatorname*{outdeg}v-1\right)  !,
\]
and therefore $w_{i}=w_{j}$, which proves Theorem
\ref{thm.arborescences.equal}.

\newpage

\begin{exercise}
\label{exe.arborescences.wheel}Let $m$ be a positive integer. Let $W_{m}$ be
the simple digraph with $m+1$ vertices $0,1,\ldots,m$ and the following $3m$
arcs:%
\begin{align*}
&  \left(  1,2\right)  ,\left(  2,3\right)  ,\ldots,\left(  m-1,m\right)
,\left(  m,1\right)  ;\\
&  \left(  0,i\right)  \ \ \ \ \ \ \ \ \ \ \text{for each }i\in\left[
m\right]  ;\\
&  \left(  i,0\right)  \ \ \ \ \ \ \ \ \ \ \text{for each }i\in\left[
m\right]  .
\end{align*}
(Visually speaking, $W_{m}$ consists of a cycle that traverses $m$ vertices
$1,2,\ldots,m$, as well as a \textquotedblleft center vertex\textquotedblright%
\ $0$ which is joined to each of these $m$ vertices by one edge in each
direction. For example, here is how $W_{6}$ looks like:%
\[%
%TCIMACRO{\TeXButton{wheel digraph W6}{\xymatrix{
%& 2 \ar[rr] \ar@/^/[dr] & & 3 \ar[dr] \ar@/^/[dl] \\
%1 \ar[ur] \ar@/^/[rr] & & 0 \ar@/^/[ul] \ar@/^/[ur] \ar@/^/[rr] \ar@
%/^/[dr] \ar@/^/[dl] \ar@/^/[ll] & & 4 \ar[dl] \ar@/^/[ll] \\
%& 6 \ar[lu] \ar@/^/[ur] & & 5 \ar[ll] \ar@/^/[ul]
%}}}%
%BeginExpansion
\xymatrix{
& 2 \ar[rr] \ar@/^/[dr] & & 3 \ar[dr] \ar@/^/[dl] \\
1 \ar[ur] \ar@/^/[rr] & & 0 \ar@/^/[ul] \ar@/^/[ur] \ar@/^/[rr] \ar@
/^/[dr] \ar@/^/[dl] \ar@/^/[ll] & & 4 \ar[dl] \ar@/^/[ll] \\
& 6 \ar[lu] \ar@/^/[ur] & & 5 \ar[ll] \ar@/^/[ul]
}%
%EndExpansion
.
\]
And here is a $0$-arborescence of $W_{6}$:%
\begin{equation}%
%TCIMACRO{\TeXButton{wheel digraph W6}{\xymatrix{
%& 2 \ar[rr] & & 3 \\
%1 \ar[ur] & & 0 \ar@/^/[rr] \ar@/^/[dl] \ar@/^/[ll] & & 4 \ar[dl] \\
%& 6 & & 5
%}}}%
%BeginExpansion
\xymatrix{
& 2 \ar[rr] & & 3 \\
1 \ar[ur] & & 0 \ar@/^/[rr] \ar@/^/[dl] \ar@/^/[ll] & & 4 \ar[dl] \\
& 6 & & 5
}%
%EndExpansion
, \label{eq.exe.arborescences.wheel.ex2}%
\end{equation}
where of course we draw a $0$-arborescence $B$ by drawing the digraph $\left(
V,B\right)  $ with $V$ being the vertex set of $W_{m}$.)

\textbf{(a)} Compute the number of $0$-arborescences of $W_{m}$.

\textbf{(b)} Let $i\in\left[  m\right]  $. Compute the number of
$i$-arborescences of $W_{m}$.

[For example, if $m=3$, then both answers are $7$, and the $0$-arborescenses
of $W_{3}$ are%
\begin{align*}
&  \left\{  \left(  0,1\right)  ,\left(  0,2\right)  ,\left(  0,3\right)
\right\}  ,\ \ \ \ \ \ \ \ \ \ \left\{  \left(  0,1\right)  ,\left(
0,2\right)  ,\left(  2,3\right)  \right\}  ,\\
&  \left\{  \left(  0,1\right)  ,\left(  0,3\right)  ,\left(  1,2\right)
\right\}  ,\ \ \ \ \ \ \ \ \ \ \left\{  \left(  0,1\right)  ,\left(
1,2\right)  ,\left(  2,3\right)  \right\}  ,\\
&  \left\{  \left(  0,2\right)  ,\left(  0,3\right)  ,\left(  3,1\right)
\right\}  ,\ \ \ \ \ \ \ \ \ \ \left\{  \left(  0,2\right)  ,\left(
2,3\right)  ,\left(  3,1\right)  \right\}  ,\\
&  \left\{  \left(  0,3\right)  ,\left(  1,2\right)  ,\left(  3,1\right)
\right\}  .
\end{align*}
]
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.arborescences.wheel} (sketched).]Let $V$ be the
set of all vertices of $W_{m}$. We classify the $3m$ arcs of $W_{m}$ into the
following three classes:

\begin{itemize}
\item The arcs $\left(  1,2\right)  ,\left(  2,3\right)  ,\ldots,\left(
m-1,m\right)  ,\left(  m,1\right)  $ of $W_{m}$ will be called the
\textit{circle-arcs}. Note that there are $m$ of these arcs. Note also that
for any two vertices $i,j\in\left[  m\right]  $, there is exactly one path
from $i$ to $j$ that uses only circle-arcs. This path will be denoted by
$P_{i,j}$.

\item The arcs $\left(  0,1\right)  ,\left(  0,2\right)  ,\ldots,\left(
0,m\right)  $ of $W_{m}$ will be called the \textit{centrifugal arcs}.

\item The arcs $\left(  1,0\right)  ,\left(  2,0\right)  ,\ldots,\left(
m,0\right)  $ of $W_{m}$ will be called the \textit{centripetal arcs}.
\end{itemize}

Also, if $i\in\left[  m\right]  $, then $i^{-}$ shall denote the source of the
unique circle-arc whose target is $i$. Thus, $i^{-}=i-1$ when $i>1$, whereas
$1^{-}=m$.

Also, if $i\in\left[  m\right]  $, then $i^{+}$ shall denote the source of the
unique circle-arc whose source is $i$. Thus, $i^{+}=i+1$ when $i<m$, whereas
$m^{+}=1$.

In the following, if $u$ is a vertex of $W_{m}$, then \textquotedblleft%
$u$-arborescence\textquotedblright\ will always mean \textquotedblleft%
$u$-arborescence of $W_{m}$\textquotedblright.

\textbf{(a)} This number is $2^{m}-1$.

\textit{Proof.} If $S$ is any nonempty subset of $\left[  m\right]  $, then
the $S$\textit{-spider} shall mean the subset of $A$ consisting of the
following arcs:

\begin{itemize}
\item the $k$ centrifugal arcs $\left(  0,i\right)  $ for all $i\in S$;

\item the $m-k$ circle-arcs $\left(  i^{-},i\right)  $ for all $i\notin S$.
\end{itemize}

For example, here is how the $\left\{  1,2,4\right\}  $-spider in $W_{6}$
looks like:%
\[%
%TCIMACRO{\TeXButton{a spider}{\xymatrix{
%& 2 \ar[rr] & & 3 \\
%1 & & 0 \ar@/^/[ul] \ar@/^/[rr] \ar@/^/[ll] & & 4 \ar[dl] \\
%& 6 & & 5 \ar[ll]
%}}}%
%BeginExpansion
\xymatrix{
& 2 \ar[rr] & & 3 \\
1 & & 0 \ar@/^/[ul] \ar@/^/[rr] \ar@/^/[ll] & & 4 \ar[dl] \\
& 6 & & 5 \ar[ll]
}%
%EndExpansion
.
\]
Also, the $0$-arborescence of $W_{6}$ shown in
(\ref{eq.exe.arborescences.wheel.ex2}) is actually the $\left\{
1,4,6\right\}  $-spider.

It is easy to see that for every nonempty subset $S$ of $\left[  m\right]  $,
the $S$-spider is a $0$-arborescence. Thus, we have found $2^{m}-1$ many
$0$-arborescences (one for each nonempty subset $S$ of $\left[  m\right]  $),
and they are all distinct (indeed, we can recover $S$ from the $S$-spider by
looking at the centrifugal arcs appearing in the $S$-spider). Thus, the number
of $0$-arborescences of $W_{m}$ is at least $2^{m}-1$. In order to complete
this proof, we only need to check that these are the only $0$-arborescences.
In other words, we only need to check that each $0$-arborescence is an
$S$-spider for some nonempty subset $S$ of $\left[  m\right]  $.

Let $B$ be a $0$-arborescence. We want to show that $B$ is an $S$-spider for
some nonempty subset $S$ of $\left[  m\right]  $. Indeed, let $S$ be the set
of all $i\in\left[  m\right]  $ such that $B$ contains the centrifugal arc
$\left(  0,i\right)  $. Then, $S$ is a nonempty subset of $\left[  m\right]  $
(indeed, it must be nonempty, since some centrifugal arc needs to be used in
order to escape $0$). Clearly, $B$ cannot contain any centripetal arcs (by
Lemma \ref{lem.arborescences.1in} \textbf{(a)}, applied to $D=W_{m}$ and
$u=0$). Moreover, for each $i\in S$, the circle-arc $\left(  i^{-},i\right)  $
is not contained in $B$ (since that would cause $B$ to contain \textbf{two}
different arcs with target $i$, which would contradict Lemma
\ref{lem.arborescences.1in} \textbf{(b)}). Meanwhile, for each $i\in\left[
m\right]  \setminus S$, the circle-arc $\left(  i^{-},i\right)  $ is contained
in $B$ (by Lemma \ref{lem.arborescences.1in} \textbf{(b)} again, because the
centrifugal arc $\left(  0,i\right)  $ is not in $B$). This shows that the
arcs contained in $B$ are precisely the arcs that are contained in the
$S$-spider. Hence, $B$ is the $S$-spider. This proves what we wanted to show.
Thus, Exercise \ref{exe.arborescences.wheel} \textbf{(a)} is solved.

\textbf{(b)} This number is $2^{m}-1$ as well.

\textit{Proof.} This can be shown similarly to how we proved part \textbf{(a)}
above, but the argument will be much messier due to the asymmetry of the
situation. Instead, here are two different proofs, using Theorem
\ref{thm.arborescences.harmonic} and Theorem \ref{thm.arborescences.equal} instead.

\textit{First proof of the fact that the number of }$i$\textit{-arborescences
}$B$ \textit{of }$W_{m}$\textit{ is }$2^{m}-1$\textit{:} For any vertex $u$ of
$D$, we let $w_{u}$ be the number of $u$-arborescences of $D$. Then, Theorem
\ref{thm.arborescences.harmonic} shows that%
\begin{equation}
\sum_{j\in V}a_{i,j}w_{j}=\left(  \sum_{k\in V}a_{k,i}\right)  w_{i}.
\label{sol.arborescences.wheel.ex2.b.2nd.1}%
\end{equation}


But the digraph $W_{m}$ has a rotational symmetry: Specifically, there is a
digraph isomorphism from $W_{m}$ to $W_{m}$ that sends the vertices
$0,1,2,\ldots,m$ to $0,i,i+1,\ldots,m,1,2,\ldots,i-1$, respectively. (Visually
speaking, it just rotates the circumference of the circle so that vertex $1$
falls onto vertex $i$.) Thus, $w_{i}=w_{1}$. Similarly, $w_{j}=w_{1}$ for each
$j\in\left[  m\right]  $. In other words, $w_{1}=w_{2}=\cdots=w_{m}$. Now,
(\ref{sol.arborescences.wheel.ex2.b.2nd.1}) yields%
\begin{align*}
\left(  \sum_{k\in V}a_{k,i}\right)  w_{i}  &  =\sum_{j\in V}a_{i,j}w_{j}\\
&  =\underbrace{a_{i,0}}_{=1}\underbrace{w_{0}}_{\substack{=2^{m}-1\\\text{(by
our answer to}\\\text{part \textbf{(a)})}}}+\underbrace{a_{i,i^{+}}}%
_{=1}\underbrace{w_{i^{+}}}_{\substack{=w_{i}\\\text{(since }w_{1}%
=w_{2}=\cdots=w_{m}\text{)}}}+\sum_{\substack{j\in V;\\j\notin\left\{
0,i^{+}\right\}  }}\underbrace{a_{i,j}}_{=0}w_{j}\\
&  =\left(  2^{m}-1\right)  +w_{i},
\end{align*}
so that%
\[
\left(  2^{m}-1\right)  +w_{i}=\underbrace{\left(  \sum_{k\in V}%
a_{k,i}\right)  }_{=2}w_{i}=2w_{i}.
\]
Subtracting $w_{i}$ from this equality, we find $2^{m}-1=w_{i}$, so that
$w_{i}=2^{m}-1$, qed.

\textit{Second proof of the fact that the number of }$i$\textit{-arborescences
}$B$ \textit{of }$W_{m}$\textit{ is }$2^{m}-1$\textit{:} Each vertex $v$ of
$W_{m}$ satisfies $\operatorname*{indeg}v=\operatorname*{outdeg}v$ (namely,
both $\operatorname*{indeg}v$ and $\operatorname*{outdeg}v$ equal $%
\begin{cases}
m, & \text{if }v=0;\\
2, & \text{if }v\neq0
\end{cases}
$). For any vertex $u$ of $W_{m}$, we let $w_{u}$ be the number of
$u$-arborescences of $W_{m}$. Then, Theorem \ref{thm.arborescences.equal}
shows that $w_{i}=w_{j}$ for every vertex $j$ of $D$. Applying this to $j=0$,
we obtain $w_{i}=w_{0}=2^{m}-1$ (because in part \textbf{(a)} of this
exercise, we have proven that the number of $0$-arborescences of $W_{m}$ is
$2^{m}-1$). Qed.

\begin{noncompile}
\textit{Proof (rough outline).} We can construct any $i$-arborescence $B$ of
$W_{m}$ by the following algorithm:

\begin{itemize}
\item Choose any vertex $j\in\left[  m\right]  $ to be the source of the
unique centripetal arc in $B$. (There must be a unique centripetal arc in $B$,
by Lemma \ref{lem.arborescences.1in} \textbf{(b)}.) Notice that this forces
all the arcs of the path $P_{i,j}$ to belong to $B$ (since otherwise, there
would be no walk from $i$ to $j$ in $\left(  V,B\right)  $).

Instead of choosing $j$, it is actually better to choose the length $k$ of the
path $P_{i,j}$; this length $k$ will be an integer between $0$ and $m-1$.
Then, $j$ is uniquely determined as the unique vertex in $\left[  m\right]  $
that is obtained by following $k$ circle-arcs from $i$.

\item Choose the set $S$ of targets of all centrifugal arcs in $B$. This must
be a nonempty subset of $\left[  m\right]  \setminus P_{i,j}$, unless $k=m-1$,
in which case it is the empty set. Thus, we have $%
\begin{cases}
2^{m-k-1}-1, & \text{if }k\neq m-1;\\
1, & \text{if }k=m-1
\end{cases}
$ options at this step.

\item Finally, the circle-arcs in $B$ must be the arcs $\left(  \ell^{-}%
,\ell\right)  $ for $\ell\in\left[  m\right]  \setminus\left(  P_{i,j}\cup
S\right)  $.
\end{itemize}

Thus, the total number of $i$-arborescences of $W_{m}$ is%
\begin{align*}
&  \sum_{k=0}^{m-1}%
\begin{cases}
2^{m-k-1}-1, & \text{if }k\neq m-1;\\
1, & \text{if }k=m-1
\end{cases}
\\
&  =\sum_{k=0}^{m-2}\left(  2^{m-k-1}-1\right)  +1=\sum_{k=1}^{m-1}\left(
2^{k}-1\right)  +1\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have substituted }m-k-1\text{
for }k\text{ in the sum}\right) \\
&  =\underbrace{\sum_{k=1}^{m-1}2^{k}}_{=2^{m}-1-1}-\left(  m-1\right)
+1=2^{m}-1
\end{align*}
The above is somewhat incorrect.
\end{noncompile}
\end{proof}

\subsection{Back to undirected graphs}

In the following exercises, we will use the following definitions:

\begin{definition}
\label{def.intro.path-graph} For each $n\in\mathbb{N}$, we define the
\textit{$n$-th path graph} to be the simple graph
\begin{align*}
&  \left(  \left\{  1,2,\ldots,n\right\}  ,\left\{  \left\{  i,i+1\right\}
\ \mid\ i\in\left\{  1,2,\ldots,n-1\right\}  \right\}  \right) \\
&  =\left(  \left\{  1,2,\ldots,n\right\}  ,\left\{  \left\{  1,2\right\}
,\left\{  2,3\right\}  ,\ldots,\left\{  n-1,n\right\}  \right\}  \right)  .
\end{align*}
This graph is denoted by $P_{n}$. It has $n$ vertices and $n-1$ edges (unless
$n=0$, in which case it has $0$ edges). Here is a drawing of $P_{4}$:
\[
\xymatrix{ 1 \are[r] & 2 \are[r] & 3 \are[r] & 4 }.
\]

\end{definition}

\begin{definition}
\label{def.intro.cycle-graph} For each integer $n>1$, we define the
\textit{$n$-th cycle graph} to be the simple graph
\begin{align*}
&  \left(  \left\{  1,2,\ldots,n\right\}  ,\left\{  \left\{  i,i+1\right\}
\ \mid\ i\in\left\{  1,2,\ldots,n-1\right\}  \right\}  \cup\left\{
n,1\right\}  \right) \\
&  =\left(  \left\{  1,2,\ldots,n\right\}  ,\left\{  \left\{  1,2\right\}
,\left\{  2,3\right\}  ,\ldots,\left\{  n-1,n\right\}  ,\left\{  n,1\right\}
\right\}  \right)  .
\end{align*}
This graph is denoted by $C_{n}$. It has $n$ vertices and $%
\begin{cases}
n, & \text{ if }n\geq3;\\
1, & \text{ if }n=2
\end{cases}
$ edges. Here is a drawing of $C_{6}$:
\[
\xymatrix{ & 1 \are[r] & 2 \are[rd] \\ 6 \are[ru] & & & 3 \are[ld] \\ & 5 \are[lu] & 4 \are[l] }.
\]

\end{definition}

\subsection{Chromatic polynomials of complete bipartite graphs}

For the definition and properties of the chromatic polynomial of a simple
graph, see Exercise 4 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17s/mt2s.pdf}{Spring 2017
Math 5707 midterm \#2}. In a nutshell:

\begin{itemize}
\item If $G=\left(  V,E\right)  $ is a simple graph, then the
\textit{chromatic polynomial} $\chi_{G}$ of $G$ is a polynomial in a single
indeterminate $x$ (with integer coefficients) defined by%
\[
\chi_{G}=\sum_{F\subseteq E}\left(  -1\right)  ^{\left\vert F\right\vert
}x^{\operatorname{conn}\left(  V,F\right)  }.
\]
(Here, as usual, $\operatorname{conn}H$ denotes the number of connected
components of any graph $H$.)

We could easily extend this definition to multigraphs, but I don't want to
carry the extra notation around.

\item The main property of chromatic polynomials in the following: If
$G=\left(  V,E\right)  $ is a graph, and if $k\in\mathbb{N}$, then $\chi
_{G}\left(  k\right)  $ is the number of all proper $k$%
-colorings\footnote{Recall that a \textit{$k$-coloring} of $G$ means a map
$f:V\rightarrow\left\{  1,2,\ldots,k\right\}  $. (The image $f\left(
v\right)  $ of a vertex $v\in V$ under this map is called the \textit{color}
of $v$ under this $k$-coloring $f$.) A $k$-coloring $f$ of $G$ is said to be
\textit{proper} if each edge $\left\{  u,v\right\}  $ of $G$ satisfies
$f\left(  u\right)  \neq f\left(  v\right)  $. (In other words, a $k$-coloring
$f$ of $G$ is proper if and only if no two adjacent vertices share the same
color.)} of $G$. Note that this property uniquely determines $\chi_{G}$,
because any polynomial in a single indeterminate $x$ is uniquely determined by
its values on all nonnegative integers.

\item For any $n\in\mathbb{N}$, the complete graph $K_{n}$ (that is, the
simple graph with $n$ vertices $1,2,\ldots,n$ and all possible edges $\left\{
i,j\right\}  $ with $1\leq i<j\leq n$) has chromatic polynomial $\chi_{K_{n}%
}=x\left(  x-1\right)  \cdots\left(  x-n+1\right)  $.

\item If $T$ is a tree with $n$ vertices, then $\chi_{T}=x\left(  x-1\right)
^{n-1}$. Thus, in particular, for any positive integer $n$, the path graph
$P_{n}$ (see Definition \ref{def.intro.path-graph}) has characteristic
polynomial $\chi_{P_{n}}=x\left(  x-1\right)  ^{n-1}$ (since it is a tree with
$n$ vertices).

\item If $n>1$ is an integer, then the chromatic polynomial of the cycle graph
$C_{n}$ (see Definition \ref{def.intro.cycle-graph}) is $\chi_{C_{n}}=\left(
x-1\right)  ^{n}+\left(  -1\right)  ^{n}\left(  x-1\right)  $. (This is
Exercise 2 \textbf{(a)} on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17s/mt3s-ogden.pdf}{Spring
2017 Math 5707 midterm \#3}.)
\end{itemize}

\begin{definition}
Let $n\in\mathbb{N}$ and $m\in\mathbb{N}$. The graph $K_{n,m}$ is defined to
be the simple graph with $n+m$ vertices%
\[
1,2,\ldots,n,-1,-2,\ldots,-m
\]
and $nm$ edges%
\[
\left\{  i,-j\right\}  \ \ \ \ \ \ \ \ \ \ \text{for all }i\in\left[
n\right]  \text{ and }j\in\left[  m\right]  .
\]
(Note that $\left(  K_{n,m};\left\{  1,2,\ldots,n\right\}  ,\left\{
-1,-2,\ldots,-m\right\}  \right)  $ is a bipartite graph, called the
\textit{complete bipartite graph}.)
\end{definition}

For example, the graph $K_{2,3}$ is%
\[%
%TCIMACRO{\TeXButton{K2,3 graph}{\xymatrix{
%1 \are[d] \are[rd] \are[rrd] & 2 \are[ld] \are[d] \are[rd] \\
%-1 & -2 & -3
%}}}%
%BeginExpansion
\xymatrix{
1 \are[d] \are[rd] \are[rrd] & 2 \are[ld] \are[d] \are[rd] \\
-1 & -2 & -3
}%
%EndExpansion
.
\]


\begin{exercise}
\label{exe.chrompol.Knm}Let $n\in\mathbb{N}$ and $m\in\mathbb{N}$.

\textbf{(a)} Prove that the chromatic polynomial of $K_{n,m}$ is%
\[
\chi_{K_{n,m}}=\sum_{i=0}^{n}\operatorname*{sur}\left(  n,i\right)  \dbinom
{x}{i}\left(  x-i\right)  ^{m}.
\]
(Recall that $\operatorname*{sur}\left(  n,i\right)  $ denotes the number of
all surjections from $\left[  n\right]  $ to $\left[  i\right]  $.)

\textbf{(b)} Prove that%
\[
\sum_{i=0}^{n}\operatorname*{sur}\left(  n,i\right)  \dbinom{x}{i}\left(
x-i\right)  ^{m}=\sum_{i=0}^{m}\operatorname*{sur}\left(  m,i\right)
\dbinom{x}{i}\left(  x-i\right)  ^{n}.
\]

\end{exercise}

\begin{remark}
Applying Exercise \ref{exe.chrompol.Knm} \textbf{(b)} to $n=0$, we recover the
identity%
\[
x^{m}=\sum_{i=0}^{m}\operatorname*{sur}\left(  m,i\right)  \dbinom{x}{i},
\]
which was Theorem 3.15 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/4707-2018feb21.pdf}{the
class of February 21}.
\end{remark}

\subsection{Counting independent sets}

Now let us return to independent sets of graphs.

\begin{definition}
Let $G$ be a graph.

\textbf{(a)} An \textit{independent set} of $G$ means a set $S$ of vertices of
$G$ such that no two distinct elements of $S$ are adjacent.

\textbf{(b)} We let $\operatorname*{ind}G$ be the number of all independent
sets of $G$.
\end{definition}

There are no good formulas for $\operatorname*{ind}G$ in general, but we can
always try to compute it when $G$ is a particularly simple type of graph. For
example, if $G$ is the path graph $P_{n}$ for some $n\in\mathbb{N}$, then the
independent sets of $G$ are precisely the lacunar subsets of $\left[
n\right]  $, and thus $\operatorname*{ind}G$ is the Fibonacci number $f_{n+2}$
(by Proposition 1.22 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/4707-2018feb5.pdf}{the
February 5 class}). The independent sets of the cycle graph $C_{n}$ are the
lacunar subsets of $\left[  n\right]  $ which don't contain $1$ and $n$
simultaneously (i.e., they can contain at most one of $1$ and $n$). The
following definition will help counting them:

\begin{definition}
Let $G$ be a graph. Let $S$ be a set of vertices of $G$. Then, $G\setminus S$
will denote the graph obtained from $G$ by removing all vertices in $S$ (along
with all edges that use these vertices).

(More rigorously: If $G$ is a simple graph $\left(  V,E\right)  $, then
$G\setminus S$ is the simple graph $\left(  V\setminus S,E^{\prime}\right)  $,
where $E^{\prime}$ is the set of all edges $e\in E$ such that no endpoint of
$e$ belongs to $S$. If $G$ is a multigraph $\left(  V,E,\varphi\right)  $,
then $G\setminus S$ is the multigraph $\left(  V\setminus S,E^{\prime}%
,\varphi\mid_{E^{\prime}}\right)  $, where $E^{\prime}$ is the set of all
edges $e\in E$ such that no endpoint of $e$ belongs to $S$.)
\end{definition}

For example, if $G$ is the graph%
\[%
%TCIMACRO{\TeXButton{6-vertex graph}{\xymatrix{
%1 \are[r] \are[d] & 3 \are[d] \are[r] & 5 \are[d] \\
%2 \are[r] & 4 \are[r] & 6
%}}}%
%BeginExpansion
\xymatrix{
1 \are[r] \are[d] & 3 \are[d] \are[r] & 5 \are[d] \\
2 \are[r] & 4 \are[r] & 6
}%
%EndExpansion
,
\]
then $G\setminus\left\{  2,3\right\}  $ is the graph%
\[%
%TCIMACRO{\TeXButton{smaller graph}{\xymatrix{
%1 & & 5 \are[d] \\
%& 4 \are[r] & 6
%}}}%
%BeginExpansion
\xymatrix{
1 & & 5 \are[d] \\
& 4 \are[r] & 6
}%
%EndExpansion
.
\]


\begin{exercise}
\label{exe.ind-number.Cn}\textbf{(a)} Let $v$ be a vertex of a graph $G$. Let
$N\left(  v\right)  $ be the set of all neighbors of $v$. Let $N^{+}\left(
v\right)  =\left\{  v\right\}  \cup N\left(  v\right)  $. Prove that%
\[
\operatorname*{ind}G=\operatorname*{ind}\left(  G\setminus\left\{  v\right\}
\right)  +\operatorname*{ind}\left(  G\setminus\left(  N^{+}\left(  v\right)
\right)  \right)  .
\]


\textbf{(b)} Compute $\operatorname*{ind}\left(  C_{n}\right)  $ for each
$n\geq2$ (in terms of the Fibonacci sequence).
\end{exercise}

\begin{remark}
\textbf{(a)} It is instructive to see what Exercise \ref{exe.ind-number.Cn}
\textbf{(a)} says when $G$ is a path graph. Let $n>1$ be an integer, and let
$G$ be the path graph $P_{n}$. Let $v\in\left[  n\right]  $ (so that $v$ is a
vertex of $G$). If $v=n$, then $G\setminus\left\{  v\right\}  =P_{n-1}$ and
$G\setminus\left(  N^{+}\left(  v\right)  \right)  =P_{n-2}$ (since
$N^{+}\left(  v\right)  =\left\{  n,n-1\right\}  $ in this case), so that
Exercise \ref{exe.ind-number.Cn} \textbf{(a)} yields%
\[
\operatorname*{ind}\left(  P_{n}\right)  =\operatorname*{ind}\left(
P_{n-1}\right)  +\operatorname*{ind}\left(  P_{n-2}\right)  .
\]
This is precisely the recurrence equation of the Fibonacci numbers. Thus, we
obtain a new (inductive) proof of the fact that
\begin{equation}
\operatorname*{ind}\left(  P_{n}\right)  =f_{n+2}\ \ \ \ \ \ \ \ \ \ \text{for
each }n\in\mathbb{N}. \label{rmk.ind-number.Cn.fib-for}%
\end{equation}


However, we can also apply Exercise \ref{exe.ind-number.Cn} \textbf{(a)} to
another vertex $v$. Let $v\in\left\{  2,3,\ldots,n-1\right\}  $. Then,
$G\setminus\left\{  v\right\}  $ is a disconnected graph looking as follows:%
\[%
%TCIMACRO{\TeXButton{two paths}{\xymatrix{
%1 \are[r] & 2 \are[r] & \cdots\are[r] & v-1 & v+1 \are[r] & v+2 \are
%[r] & \cdots\are[r] & n
%}}}%
%BeginExpansion
\xymatrix{
1 \are[r] & 2 \are[r] & \cdots\are[r] & v-1 & v+1 \are[r] & v+2 \are
[r] & \cdots\are[r] & n
}%
%EndExpansion
.
\]
We can treat this graph as a \textquotedblleft disjoint
union\textquotedblright\ of two path graphs, one of which is $P_{v-1}$ while
the other is $P_{n-v}$ \textquotedblleft in all but name\textquotedblright%
\ (its vertices are called $v+1,v+2,\ldots,n$ rather than $1,2,\ldots,n-v$,
but otherwise it is identical to $P_{n-v}$). To construct an independent set
of $G\setminus\left\{  v\right\}  $, we thus just need to choose an
independent set of the former path graph $P_{v-1}$ and an independent set of
the latter path grad $P_{n-v}$ (with vertices renamed as $v+1,v+2,\ldots,n$),
and take the union of these two independent sets. Hence,%
\[
\operatorname*{ind}\left(  G\setminus\left\{  v\right\}  \right)
=\operatorname*{ind}\left(  P_{v-1}\right)  \cdot\operatorname*{ind}\left(
P_{n-v}\right)  .
\]
A similar argument shows that the graph $G\setminus\left(  N^{+}\left(
v\right)  \right)  $ has the form%
\[%
%TCIMACRO{\TeXButton{two paths}{\xymatrix{
%1 \are[r] & 2 \are[r] & \cdots\are[r] & v-2 & v+2 \are[r] & v+3 \are
%[r] & \cdots\are[r] & n
%}}}%
%BeginExpansion
\xymatrix{
1 \are[r] & 2 \are[r] & \cdots\are[r] & v-2 & v+2 \are[r] & v+3 \are
[r] & \cdots\are[r] & n
}%
%EndExpansion
\]
(again, a \textquotedblleft disjoint union\textquotedblright\ of two path
graphs, which this time are $P_{v-2}$ and $P_{n-v-1}$), and thus%
\[
\operatorname*{ind}\left(  G\setminus\left(  N^{+}\left(  v\right)  \right)
\right)  =\operatorname*{ind}\left(  P_{v-2}\right)  \cdot\operatorname*{ind}%
\left(  P_{n-v-1}\right)  .
\]
Hence, Exercise \ref{exe.ind-number.Cn} \textbf{(a)} becomes%
\begin{align*}
\operatorname*{ind}G  &  =\underbrace{\operatorname*{ind}\left(
G\setminus\left\{  v\right\}  \right)  }_{=\operatorname*{ind}\left(
P_{v-1}\right)  \cdot\operatorname*{ind}\left(  P_{n-v}\right)  }%
+\underbrace{\operatorname*{ind}\left(  G\setminus\left(  N^{+}\left(
v\right)  \right)  \right)  }_{=\operatorname*{ind}\left(  P_{v-2}\right)
\cdot\operatorname*{ind}\left(  P_{n-v-1}\right)  }\\
&  =\operatorname*{ind}\left(  P_{v-1}\right)  \cdot\operatorname*{ind}\left(
P_{n-v}\right)  +\operatorname*{ind}\left(  P_{v-2}\right)  \cdot
\operatorname*{ind}\left(  P_{n-v-1}\right)  .
\end{align*}
Since $G=P_{n}$, this rewrites as%
\[
\operatorname*{ind}\left(  P_{n}\right)  =\operatorname*{ind}\left(
P_{v-1}\right)  \cdot\operatorname*{ind}\left(  P_{n-v}\right)
+\operatorname*{ind}\left(  P_{v-2}\right)  \cdot\operatorname*{ind}\left(
P_{n-v-1}\right)  .
\]
Using the equality (\ref{rmk.ind-number.Cn.fib-for}), we can rewrite this as%
\[
f_{n+2}=f_{\left(  v-1\right)  +2}\cdot f_{\left(  n-v\right)  +2}+f_{\left(
v-2\right)  +2}\cdot f_{\left(  n-v-1\right)  +2}=f_{v+1}f_{n-v+2}%
+f_{v}f_{n-v+1}.
\]
Applying this to $v=a$ and $n=a+b-1$, we conclude that%
\[
f_{a+b+1}=f_{a+1}f_{b+1}+f_{a}f_{b}\ \ \ \ \ \ \ \ \ \ \text{for all }%
a\in\mathbb{N}\text{ and }b\in\mathbb{N}.
\]
(To be more precise, we have only proven this in the case when $a>1$ and
$b>1$; but all other cases are easy.) Thus, we have recovered the claim of
Exercise 3 \textbf{(e)} on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw3s.pdf}{midterm \#1}.

\textbf{(b)} We can similarly count independent sets \textbf{of a given size}.
For $C_{n}$, we find that the number of independent sets of $C_{n}$ having
size $k$ (for a given $k\in\left\{  0,1,\ldots,n-1\right\}  $) is $\dfrac
{n}{n-k}\dbinom{n-k}{k}$. This can also be proven combinatorially; see
\cite[Lemma 2.3.4]{Stanley-EC1}.
\end{remark}

\begin{thebibliography}{999999999}                                                                                        %


\bibitem[Berge91]{Berge91}Claude Berge, \textit{Graphs}, 3rd revised edition,
North-Holland 1991.

\bibitem[Bollob98]{Bollob98}B\'{e}la Bollob\'{a}s, \textit{Modern Graph
Theory}, Graduate Texts in Mathematics \#184, 1st edition, Springer 1998.

\bibitem[Grinbe17a]{diamond-talk}Darij Grinberg, \textit{The diamond lemma and
its applications (talk slides}),\newline\url{http://www.cip.ifi.lmu.de/~grinberg/algebra/diamond-talk.pdf}

\bibitem[JacGou79]{JacGou79}D. M. Jackson, I. P. Goulden, \textit{Sequence
enumeration and the de Bruijn-van Aardenne-Ehrenfest-Smith-Tutte theorem},
Canad. J. Math. 31(1979), pp. 488--495,\newline\url{https://doi.org/10.4153/CJM-1979-054-x}

\bibitem[MO289300]{MO289300}Darij Grinberg, \textit{MathOverflow post
\#289300},\newline\url{https://mathoverflow.net/a/289320/}

\bibitem[Klings11]{Klings11}Paul Klingsberg, \textit{The BEST Theorem}%
,\newline\url{http://people.sju.edu/~pklingsb/best.pdf}

\bibitem[Sahi13]{Sahi13}\href{https://arxiv.org/abs/1309.4047v1}{Siddhartha
Sahi, \textit{Harmonic vectors and matrix tree theorems}, arXiv:1309.4047v1}.

\bibitem[Stan11]{Stanley-EC1}Richard Stanley, \textit{Enumerative
Combinatorics, volume 1}, Second edition, version of 15 July 2011. Available
at \url{http://math.mit.edu/~rstan/ec/} .
\end{thebibliography}


\end{document}