\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 01, 2018 19:08:13}
%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}

due date: Wednesday 2 May 2018 at the beginning of class, or before that by
email or moodle

Please solve \textbf{at most 3} of the 5 exercises!

\textbf{Collaboration is not allowed!}
\end{center}

%

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


\bigskip

Please write your name on each page. Feel free to use LaTeX
(\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw-template.tex}{here} is
a sample file with lots of amenities included).

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\}  $.

\item We use the Iverson bracket notation.
\end{itemize}

Keep in mind that \textbf{everything you claim must be proven} (unless it was
stated in class or on previous homeworks/midterms/solutions), even if the
exercise doesn't explicitly say so.

\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}.

\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}
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)  $.)

[\textbf{Hint:} 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. Prove
that this list does the job.]
\end{exercise}

\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}

\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 simple digraph $\left(  V,A\right)  $. A
$u$\textit{-arborescence of }$D$ means a subset $B$ of $A$ such that the
digraph $\left(  V,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.

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.

\begin{exercise}
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}$:%
\[%
%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
.
\]
)

\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}

\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}{999999}                                                                                           %


\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}