\documentclass[12pt]{article}
\usepackage{amsmath,amsthm,amssymb,amsfonts,fancyhdr,multicol,mathptmx}
\usepackage{tikz}
\usetikzlibrary{arrows}
\usepackage[margin=1in]{geometry}

\renewcommand{\baselinestretch}{1.1}
\theoremstyle{plain}
\newtheorem*{theorem}{Theorem}
\newtheorem*{DMV}{Directed Multigraph Matrix Tree Theorem}
%\newtheorem*{theorem}{Theorem}
\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newtheorem{remark}{Remark}
\newtheorem*{example*}{Example}
\newtheorem*{definition*}{Definition}
\newcommand{\bp}{\begin{problem}}
\newcommand{\ep}{\end{problem}}

\newtheorem*{answer}{Answer}
\newtheorem*{lemma*}{Lemma}
\newtheorem*{theorem*}{Theorem}
\newcommand{\ba}{\begin{answer}}
\newcommand{\ea}{\end{answer}}

\newcommand{\ds}{\displaystyle}
\newcommand{\ben}{\renewcommand{\theenumi}{\alph{enumi}}\renewcommand{\labelenumi}{(\theenumi)}\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}

\newcommand{\Z}{\mathbb{Z}} 
\newcommand{\N}{\mathbb{N}} 
\newcommand{\R}{\mathbb{R}} 
\newcommand{\C}{\mathbb{C}} 



\fancyhead[L]{\Large \textbf{Math 634 Spring 2016}}
\fancyhead[R]{\large \textbf{Midterm Exam}}


\begin{document}
\pagestyle{fancy}
\fancyfoot[R,L,C]{}

\section*{A matrix-tree theorem for directed multigraphs}
In class, we stated and proved the matrix-tree theorem for ordinary graphs.  There's a version for \emph{directed multigraphs} as well.  First, you need to know what the Laplacian of a directed multigraph is.
\begin{definition*}
The \emph{Laplacian} of a directed multigraph $G$ with vertices $\{v_1, \ldots, v_n\}$ is defined to be the $n\times n$ matrix whose $(i,j)$ entry $l_{ij}$ is defined by
$$l_{ij}=\begin{cases}
\text{the outdegree $d^+(v_i)$ of $v_i$} & \text{ if $i=j$},\\
-s & \text{if $i\neq j$ and there are $s$ edges from $v_i$ to $v_j$}.
\end{cases}
$$
%the outdegree of $v_i$, and whose $i$-$j$ entry is $-s$ if there are $s$ directed edges from $v_i$ to $v_j$.
\end{definition*}

\begin{example*}Here's a picture of a directed multigraph and its Laplacian.

\begin{center}
\begin{minipage}{.3\textwidth}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3cm,
  thick,main node/.style={circle,fill=blue!10,draw,font=\sffamily\large\bfseries}]

  \node[main node] (1) {1};
  \node[main node] (2) [above of=1] {2};
   \node[main node] (3) [right of=2,node distance=4cm] {3}; 
   %\node[main node] (5) [right of=3] {5};
  \path[every node/.style={font=\sffamily\small}]
    (1)  edge  (2)
    (1)  edge [bend right=60] (3)
    (1)  edge [bend right=0] (3)
    (1)  edge [bend right=30] (3)
    (2)  edge [bend right=0] (3)
    (2)  edge [bend right=45] (1)
    (3)  edge [bend right=45] (2)
    ;
\end{tikzpicture}
\end{minipage}
\qquad
\begin{minipage}{.4\textwidth}
$$\begin{pmatrix}
4&-1&-3\\
-1 & 2 & -1\\
0 & -1 & 1
\end{pmatrix}
$$\end{minipage}
\end{center}
\end{example*}
\noindent And now here is a directed multigraph version of the matrix tree theorem:
\begin{DMV}Let $G$ be a directed multigraph, let $L$ be its Laplacian matrix, and let $L_i$ be the Laplacian matrix with the $i$-th row and $i$-th column removed.  Then the number of spanning trees oriented towards the vertex $i$ is equal to $\det(L_i)$.
\end{DMV}
\begin{example*}
In the example above, 
\begin{minipage}{.13\textwidth}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=1cm,
  thick,main node/.style={circle,inner sep=2pt,fill=blue!10,draw,font=\sffamily\tiny\bfseries}]

  \node[main node] (1) {1};
  \node[main node] (2) [above of=1] {2};
   \node[main node] (3) [right of=2,node distance=1.5cm] {3}; 
   %\node[main node] (5) [right of=3] {5};
  \path[every node/.style={font=\sffamily\small}]
    (2)  edge [bend right=45] (1)
    (3)  edge [bend right=45] (2)
    ;
\end{tikzpicture}
\end{minipage}
is the only spanning tree oriented towards the first vertex 
and $\det(L_1)=\det \begin{pmatrix}
2 & -1\\
-1 & 1
\end{pmatrix}
=1$. 
Also, there are four spanning trees oriented towards the second vertex:
\begin{minipage}{.13\textwidth}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=1cm,
  thick,main node/.style={circle,inner sep=2pt,fill=blue!10,draw,font=\sffamily\tiny\bfseries}]

  \node[main node] (1) {1};
  \node[main node] (2) [above of=1] {2};
   \node[main node] (3) [right of=2,node distance=1.5cm] {3}; 
   %\node[main node] (5) [right of=3] {5};
  \path[every node/.style={font=\sffamily\small}]
    (1)  edge  (2)
    (3)  edge [bend right=45] (2)
    ;
    \end{tikzpicture}
\end{minipage}
\begin{minipage}{.13\textwidth}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=1cm,
  thick,main node/.style={circle,inner sep=2pt,fill=blue!10,draw,font=\sffamily\tiny\bfseries}]

  \node[main node] (1) {1};
  \node[main node] (2) [above of=1] {2};
   \node[main node] (3) [right of=2,node distance=1.5cm] {3}; 
   %\node[main node] (5) [right of=3] {5};
  \path[every node/.style={font=\sffamily\small}]
    (1)  edge [bend right=0] (3)
    (3)  edge [bend right=45] (2)
    ;
    \end{tikzpicture}
\end{minipage}
\begin{minipage}{.13\textwidth}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=1cm,
  thick,main node/.style={circle,inner sep=2pt,fill=blue!10,draw,font=\sffamily\tiny\bfseries}]

  \node[main node] (1) {1};
  \node[main node] (2) [above of=1] {2};
   \node[main node] (3) [right of=2,node distance=1.5cm] {3}; 
   %\node[main node] (5) [right of=3] {5};
  \path[every node/.style={font=\sffamily\small}]
    (1)  edge [bend right=30] (3)
    (3)  edge [bend right=45] (2)
    ;
    \end{tikzpicture}
\end{minipage}
\begin{minipage}{.13\textwidth}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=1cm,
  thick,main node/.style={circle,inner sep=2pt,fill=blue!10,draw,font=\sffamily\tiny\bfseries}]

  \node[main node] (1) {1};
  \node[main node] (2) [above of=1] {2};
   \node[main node] (3) [right of=2,node distance=1.5cm] {3}; 
   %\node[main node] (5) [right of=3] {5};
  \path[every node/.style={font=\sffamily\small}]
    (1)  edge [bend right=60] (3)
    (3)  edge [bend right=45] (2)
    ;
    \end{tikzpicture}
\end{minipage}
and $\det(L_2)=\det \begin{pmatrix}
4 & -3\\
0 & 1
\end{pmatrix}=4$.
\end{example*}

\pagebreak
\section*{Your Problems}

\bp \textbf{[10 points]}
Let $G$ be the directed graph pictured below.  
\bigskip
\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3cm,
  thick,main node/.style={circle,fill=blue!10,draw,font=\sffamily\large\bfseries}]

  \node[main node] (4) {4};
  \node[main node] (1) [right of=1] {1};
   \node[main node] (2) [above of=1] {2}; 
  \node[main node] (3) [right of=2] {3};
  %\node[main node] (5) [right of=3] {5};
  \path[every node/.style={font=\sffamily\small}]
    (1)  edge  [bend right=30] (2)
    (1)  edge [bend right=0] (3)
    (1)  edge [bend right=0] (4)
    (2)  edge [bend right=30] (1)
    (2)  edge [bend right=0] (3)
    (2)  edge [bend right=45] (4)
    (3)  edge [bend left=45] (1)
    (3)  edge [bend right=45] (2)
    (4)  edge [bend right=45] (1)
    (4)  edge [bend left=0] (2)
    ;
\end{tikzpicture}
\end{center}
Use the BEST Theorem and the directed-multigraph version of the matrix-tree theorem to count the Euler circuits in $G$.  \emph{Hint}: there are more than five and less than one hundred.
\ba It's worth noticing that the outdegree equals the indegree of every vertex, so the graph has Euler circuits.  The BEST theorem states that the number $c$ of Euler circuits in $G$ is given by 
$$c=t_i \prod_{j=1}^{n}(d^+(v_j)-1)!$$
where $t_i$ is the number of spanning trees oriented towards $v_i$ (the number is the same for any $i$).  By the multigraph tree-matrix theorem $t_i=\det(L_i)$ of the Laplacian reduced by removing row $i$ and column $i$.  For the given graph, we have the laplacian and the reduced laplacian $$L=\left(
\begin{array}{cccc}
 3 & -1 & -1 & -1 \\
 -1 & 3 & -1 & -1 \\
 -1 & -1 & 2 & 0 \\
 -1 & -1 & 0 & 2 \\
\end{array}
\right)\text{ and }L_1=\left(
\begin{array}{ccc}
 3 & -1 & -1 \\
 -1 & 2 & 0 \\
 -1 & 0 & 2 \\
\end{array}
\right).$$
A quick computation shows $\det(L_1)=8$, so there are $t_1=8$ spanning trees oriented towards the first vertex.  Therefore, the graph has 
$$c=8\prod_{j=1}^{4}(d^+(v_j)-1)!=8(2)!(2)!(1)!(1)!=32$$
Euler circuits.
\ea
\ep

\pagebreak

\bp Planar graphs.
\ben
\item \textbf{[5 points]} Prove that $K_{3,3}$ is nonplanar.
$K_{3,3}$ has $e=9$ edges and $v=6$ vertices.  In a planar embedding of any graph with $f$ faces, we have $v-e+f=2$.  For $K_{3,3}$, this means a planar embedding would have $f=5$ faces.  Supposing we have a planar embedding, let $f_1, \ldots, f_5$ be the number of edges in the cycles that bound each face.  Since each edge belongs to two faces, we have $2e=\sum_{i=1}^5f_i.$  Since in $K_{3,3}$, the smallest cycle has length four, and $e=9$, we have $18=f_1+f_2+f_3+f_4+f_5\leq 20$ a contradiction.
\item \textbf{[5 points]} Is the graph pictured below is planar?  If yes, prove it with a picture.  If no, identify a $K_5$ or $K_{3,3}$ minor.

\bigskip

\begin{center}
\begin{minipage}{.4\textwidth}
\begin{tikzpicture}[-,>=stealth',auto,node distance=2cm,
  thick,main node/.style={circle,fill=blue!10,draw,font=\sffamily\large\bfseries}]

  \node[main node] (1) {1};
  \node[main node] (2) [above right of=1] {2};
  \node[main node] (3) [above right of=2] {3};
  \node[main node] (4) [above of=3] {4};
  \node[main node] (5) [above of=4] {5};
  \node[main node] (6) [below right of =3] {6};
  \node[main node] (7) [below right of=6] {7};

  \path[every node/.style={font=\sffamily\small}]
    (1) edge  (5)
       (1) edge  (4)
         (1) edge  (6)
           (1) edge  (7)
    (2) edge  (5)
       (2) edge  (3)
         (2) edge  (7)
    (7) edge  (5)
       (7) edge  (4)
         (7) edge  (2)
  (6) edge  (5)
       (6) edge  (3)
         (6) edge  (1)
       (3) edge  (2)
       (3) edge  (4)
         (3) edge  (6);
\end{tikzpicture}
\end{minipage}
\end{center}


\ba This graph is planar.  Here's a picture.
\bigskip

\begin{minipage}{.4\textwidth}
\begin{tikzpicture}[-,>=stealth',auto,node distance=2cm,
  thick,main node/.style={circle,fill=blue!10,draw,font=\sffamily\large\bfseries}]

  \node[main node] (1) {1};
  \node[main node] (2) [above right of=1] {2};
  \node[main node] (3) [above right of=2] {3};
  \node[main node] (4) [above of=3] {4};
  \node[main node] (5) [above of=4] {5};
  \node[main node] (6) [below right of =3] {6};
  \node[main node] (7) [below right of=6] {7};

  \path[every node/.style={font=\sffamily\small}]
    (1) edge  (5)
       (1) edge  (4)
         (1) edge  (6)
           (1) edge  (7)
    (2) edge  (5)
       (2) edge  (3)
         (2) edge  (7)
    (7) edge  (5)
       (7) edge  (4)
         (7) edge  (2)
  (6) edge  (5)
       (6) edge  (3)
         (6) edge  (1)
       (3) edge  (2)
       (3) edge  (4)
         (3) edge  (6);
\end{tikzpicture}
\end{minipage}
\qquad
\begin{minipage}{.4\textwidth}
\begin{tikzpicture}[-,>=stealth',auto,node distance=2cm,
  thick,main node/.style={circle,fill=blue!10,draw,font=\sffamily\large\bfseries}]

  \node[main node] (1) {1};
  \node[main node] (4) [above right of=1,node distance=2.5cm] {4};
  \node[main node] (3) [above of=4,node distance=1.5cm] {3};
  \node[main node] (6) [above left of=3] {6};
  \node[main node] (2) [above right of=3] {2};
  \node[main node] (5) [above of =3,node distance=3.5cm] {5};
  \node[main node] (7) [below right of=4,node distance=2.5cm] {7};

  \path[every node/.style={font=\sffamily\small}]
    (1) edge  [bend left=60] (5)
       (1) edge  (4)
         (1) edge  (6)
           (1) edge  (7)
    (2) edge  (5)
       (2) edge  (3)
         (2) edge  (7)
    (7) edge [bend right=60]  (5)
       (7) edge  (4)
         (7) edge  (2)
  (6) edge  (5)
       (6) edge  (3)
         (6) edge  (1)
       (3) edge  (2)
       (3) edge  (4)
         (3) edge  (6);
\end{tikzpicture}
\end{minipage}
\ea



\een
\ep



\end{document}

