\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\begin{document}
{\bf Worksheet \#20; date: 11/05/2018}
{\bf MATH 55 Discrete Mathematics}
\begin{enumerate}
\item {\em (Planarity game)} {\tt https://www.jasondavies.com/planarity/}
\item {\em (Rosen 10.7.13)} Suppose that a connected planar graph has six vertices, each of degree four. Into how many regions is the plane divided by a planar representation of this graph?
\item {\em (Rosen 10.7.17)} Suppose that a connected planar simple graph with $e$ edges and $v$ vertices contains no simple circuits of length $4$ or less. Show that $e \le (5/3)v - (10/3)$ if $v \ge 4$.
\item What is the chromatic number of $K_{m, n}$ and $Q_n$?
\item Give an example of a graph where the highest degree is larger than the chromatic number.
\item An {\em edge coloring} of a graph is an assignment of colors to the edges so that edges incident with a common vertex are assigned different colors. Show that the highest degree is at most the edge chromatic number.
\item Find the edge chromatic numbers of $C_n$ and $K_n$.
\item The {\em crossing number} of a simple graph is the minimum number of crossings that can occur when this graph is drawn in a plane where no three arcs representing edges are permitted to cros at the same point. If graph $G$ has a crossing number of $100$, what is its minimum possible chromatic number?
\end{enumerate}
\end{document}