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


\ep

\bp Planar graphs.
\ben
\item \textbf{[5 points]} Prove that $K_{3,3}$ is nonplanar.

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


\een
\ep



\end{document}

