\documentclass{article}
\usepackage{amsmath,amsthm,amssymb,amsfonts,fancyhdr,epic,eepic,multicol}

\renewcommand{\baselinestretch}{1.1}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newtheorem{remark}{Remark}
\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}} 
\DeclareMathOperator{\rad}{rad}
\DeclareMathOperator{\diam}{diam}



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


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


\bp Prove that $\rad(G)\leq \diam(G)\leq 2 \rad(G)$ for any graph $G$.
\ep

\bp A little experimenting will tell you that $K_3$ is the disjoint union paths of length $1$ and $2$; $K_4$ is the disjoint union of paths of length $1, 2,$ and $3$;   $K_5$ is the disjoint union of paths of length $1, 2, 3, 4$.  Your problem:  prove that $K_n$ is the disjoint union of paths of lengths $1, 2, \ldots, n-1$.
\ep

\bp Prove that every spatial embedding of $K_{4,4}$ has a pair of linked rectangles.
\ep

\bp Prove or disprove:  Every embedding of $G=(K_{3,3}-e)+K_1$ has a pair of linked cycles.
\ep

\bp Give an example of graphs $G$ and $H$ so that $H$ is minor of $G$ but not a subgraph of a subdivision of $G$.
\ep

\bp Draw all the graphs that can be obtained from $K_6$ by $\Delta-Y$ exchanges.
\ep

\bp Are $K_5$ and $K_{3,3}$ related by $\Delta-Y$ exchanges?
\ep

\bp Find a list of forbidden minors to characterize forests.\ep

\bp The \emph{crossing number} of a graph is the smallest number of crossings that occur in a diagram of a spatial embedding of the graph.  Prove that if $G$ has crossing number $\leq 1$ then $G$ can be embedded on a torus, but not conversely.
\ep


\bp Prove that $K_n$ can be embedded on the torus if and only if $n\leq 7.$
\ep

\bp Suppose $G$ is a maximal planar graph.  That is, a planar graph such that adding any edge to $G$ results in a nonplanar graph.  Prove that every face of $G$ is a triangle.
\ep

\end{document}

