\documentclass[11pt]{article}
\usepackage{amsmath}  % this adds some math 
\usepackage{fullpage}
\usepackage{tikz}            % if you delete this, you will have trouble with the included picture. You can delete the picture.
\usepackage{chessboard}
\usepackage{hyperref}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amsmath}
\usetikzlibrary{shapes.geometric}
\usetikzlibrary{shapes.multipart}
\usetikzlibrary{arrows}

% If you have a problem, please let me know sooner than later

\newcommand\name{Chuck Norris} %%%%%%%%%%%%%%  WRITE YOUR NAME HERE



\newcounter{excounter}
\setcounter{excounter}{1}
\newcommand\question[2]{\vskip 1em  \noindent\textbf{\arabic{excounter}\addtocounter{excounter}{1}:} \emph{#1} \noindent#2}


% You can also erase this if you do not have package hancyhdr
% Fancy footnote......... 
\usepackage{fancyhdr}  %% If it does not work with your latex installation, you may just delete this...
\pagestyle{fancy}
\usepackage{lastpage}
\rfoot{\name, page \thepage/\pageref{LastPage}}
\cfoot{}
\rhead{}
\lhead{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}



%%% Note that you do not have to use this template. You can use your own writeup or make any adjustment to this one you like.
%%% This is provided only for your convenience. 


\begin{document}


{\bf MATH314  \hspace{1cm} HW 11\hfill \name}
\vskip 1em

% left column
\begin{minipage}[t]{0.75\textwidth}
Due \textbf{Apr 21} before class, \textbf{answer without justification will receive 0 points}.
The typing the HW in \LaTeX{} is optional. 
\end{minipage}
% right box for score column
\begin{minipage}[t]{0.25\textwidth}
\hfill \begin{tabular}{|r|}
\hline
\hskip 3em Score \hskip 3em \\
\hline \\ \\
\hskip 3em /60 \\
\hline
\end{tabular}
\end{minipage}



\question{}{
A graph $G$ is \textbf{outerplanar} if it can be drawn in the plane such that all vertices are incident with one face.
Here are two examples. Cycle with additional edge is outerplanar, since all vertices are incident to the exterior face.
On the other hand, $K_4$ is not outerplanar. 
\begin{center}
\begin{tikzpicture}[scale=1]
\draw[every node/.style={inner sep=1.8pt,fill,circle}]
(0,0) node[label=above:$ $](x1){}
(0,1) node[label=below:$ $](x2){}
(1,1) node[label=below:$ $](x3){}
(1,0) node[label=below:$ $](x4){}
(x1)--(x2)--(x3)--(x4)--(x1) (x1)--(x3);
\draw (0.5,-0.5)node{outerplanar};
\end{tikzpicture}
\hskip 4em
\begin{tikzpicture}[scale=1]
\draw[every node/.style={inner sep=1.8pt,fill,circle}]
(0,0) node[label=above:$ $](x1){}
(0,1) node[label=below:$ $](x2){}
(1,1) node[label=below:$ $](x3){}
(1,0) node[label=below:$ $](x4){}
(x1)--(x2)--(x3)--(x4)--(x1) (x1)--(x3)
(x2) to[out=60,in=30,looseness=2] (x4);
\draw (0.5,-0.5)node{not outerplanar};
\end{tikzpicture}
\end{center}
Show that every outerplanar graph contains a vertex of degree at most 2.
}

\textbf{Solution:}


\question{}{
A maximal outerplanar graph is a simple outerplanar graph that is not a spanning subgraph of a larger simple outerplanar graph.
Let $G$ be a maximal outerplanar graph with at least three vertices. Prove that $G$ is 2-connected.
}

\textbf{Solution:}


\question{}{
We define the \textbf{girth} of a 2-connected graph $G$ to be the length of a shortest cycle in $G$. Prove that every 2-connected $n$-vertex planar graph of girth at least $g$, $g \geq 3$, has at most $g(n-2)/(g-2)$ edges.
}

\textbf{Solution:}


\question{}{
Enumerate faces of the following graphs. The first graph is embedded in the plane with one cross-cap and the second
graph is embedded in Torus.
\begin{center}
\begin{tikzpicture}[scale=1]
\draw[every node/.style={inner sep=1.8pt,fill,circle}]
\foreach \x in {0,...,7}{(90+45*\x:1) node(x\x){} }
(x0)--(x1)--(x2)--(x3)--(x4)--(x5)--(x6)--(x7)--(x0)
(x0)--(x4)
(x1)--(x5)
(x2)--(x6)
(x3)--(x7)
(0,0) circle (5pt)
;
\draw
\foreach \x in {1,...,8}{ (90+45*\x:1.4) node{$v_{\x}$} }
;
\end{tikzpicture}
\hskip 4em
\begin{tikzpicture}[scale=1]
\draw[every node/.style={inner sep=1.8pt,fill,circle}]
(3,2) node[label=above:$x_1$](x1){}
(3,1) node[label=below:$x_2$](x2){}
(2,1) node[label=below:$x_3$](x3){}
(2,2) node[label=above:$x_4$](x4){}
(4,2) node[label=below:$x_5$](x5){}
(x1)--(x2)--(x3)--(x4)--(x1)
(x2) -- (5,1)  (0,1) to[out=0,in=90] (1,0) (1,3)to[out=270,in=120] (x4)
(x1) -- (5,2)  (0,2) -- (x4) 
(x1) to[out=140,in=270] (2.5,3)  (2.5,0) to[out=90,in=-40] (x3) 
;
\draw[-triangle 45] (0,0) -- (5,0);
\draw[-triangle 45] (0,3) -- (5,3);
\draw[-triangle 45] (0,0) -- (0,3);
\draw[-triangle 45] (5,0) -- (5,3);
\end{tikzpicture}
\end{center}
Mark the faces by either drawing several pictures and shading one face at a time or color the faces.
}

\textbf{Solution:}


\question{}{
Find embedding of $K_7$ on torus.
}


\textbf{Solution:}



\question{}{
Find two non-isomorphic embeddings of $K_5$ in\\
a) the Klein Bottle \\
b) torus.\\
Non-isomorphic embeddings means that the set of faces are different. See the following example, where a graph is twice embedded in
the plane such that the set of faces is different.
\begin{center}
\begin{tikzpicture}[scale=1]
\draw[every node/.style={inner sep=1.8pt,fill,circle}]
\foreach \x in {0,...,3}{(90*\x:1) node(x\x){} }
(x0)--(x1)--(x2)--(x3)--(x0)
(x0) -- ++(90:1)  node[label=above:$x_5$]{} 
(x2) -- ++(90:1)  node[label=above:$x_6$]{} 
;
\draw
\foreach \x in {1,...,4}{ (90*\x:1.4) node{$v_{\x}$} }
;
\end{tikzpicture}
\hskip 4em
\begin{tikzpicture}[scale=1]
\draw[every node/.style={inner sep=1.8pt,fill,circle}]
\foreach \x in {0,...,3}{(90*\x:1) node(x\x){} }
(x0)--(x1)--(x2)--(x3)--(x0)
(x0) -- ++(90:1)  node[label=above:$x_5$]{} 
(x2) -- ++(0:1)  node[label=right:$x_6$]{} 
;
\draw
\foreach \x in {1,...,4}{ (90*\x:1.4) node{$v_{\x}$} }
;
\end{tikzpicture}
\end{center}
The left embedding has a face whose boundary is cycle $v_1v_2v_3v_4$ but there is no such face in
the embedding on the right.
}


\textbf{Solution:}




\end{document}














