\documentclass[11pt]{article}

\author{Math 123}
\date{Due April 7, 2023 by midnight} 
\title{Homework 8}

\usepackage{graphicx,xypic}
\usepackage{amsthm}
\usepackage{amsmath,amssymb}
\usepackage{amsfonts}
\usepackage{xcolor}
\usepackage[margin=1in]{geometry}
\usepackage[shortlabels]{enumitem}
\newtheorem{problem}{Problem}
\renewcommand*{\proofname}{{\color{blue}Solution}}


\usepackage{fancyhdr}
\pagestyle{fancy}
\rhead{Math 123, Homework 8}

\setlength{\parindent}{0pt}
\setlength{\parskip}{1.25ex}


\begin{document}

\maketitle

% You are required to put your name here:
{\bf\Large Name:} 


\vspace{.3in}
Topics covered: planar graphs, Kuratowski's theorem

Instructions: 
\begin{itemize}
\item This assignment must be submitted on Gradescope by the due date. 
\item If you collaborate with other students (which is encouraged!), please mention this somewhere on the assignment. 
\item If you are stuck, please ask for help (from me, a TA, a classmate). Use Campuswire!  
\item You may freely use any fact proved in class. In general, you should provide proof for facts used that were not proved in class. 
\item Please restrict your solution to each problem to a single page. Usually solutions can be even shorter than that. If your solution is very long, you should think more about how to express it concisely.
\end{itemize}



\pagebreak 


\begin{problem}
Prove that the Petersen graph is not planar using Euler's formula (do not use Kuratowski's theorem). \footnote{Hint: you will need to use a problem from HW1.} 
\end{problem}

\begin{proof}

\end{proof}

\pagebreak

\begin{problem}
Let $G$ be a connected graph embedded in the plane. Prove that $G$ is bipartite if and only if every region of $\mathbb R^2\setminus G$ has an even number of sides. \footnote{Note: the boundary of a region does \underline{not} necessarily correspond to a cycle in the graph. Make sure you understand why!} \footnote{Hint: for one direction, use induction on the number of regions of $\mathbb R^2\setminus G$.} 
\end{problem}

\begin{proof}

\end{proof}


\pagebreak

\begin{problem}
Prove that the complement of a planar graph with at least $11$ vertices is nonplanar.\footnote{Hint: your solution should be very short.} Give an example of a planar graph with $8$ vertices whose complement is also planar.\footnote{Hint: in fact you can find one that is self-complementary. This should simplify your search.}
\end{problem}

\begin{proof}

\end{proof}

\pagebreak

\begin{problem}
Let $G_n$ be the graph with vertices $v_1,\ldots,v_n$ and an edge between $v_i$ and $v_j$ whenever $|i-j|\le 3$. Prove that $G_n$ is a maximal planar graph.
\end{problem}

\begin{proof}

\end{proof}


\pagebreak

{\it Submit a final project proposal. See other document for instructions. This should be submitted separately from the HW assignment: one submission per group.}


\end{document}