\documentclass{article}
\usepackage{amssymb}
\usepackage{multicol}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{verbatim}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsmath, epsfig}
\setlength{\parskip}{8pt}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
%\theoremstyle{Remark}
%\newtheorem{remark}
\renewcommand{\today}{}
\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\Lap}[1]{\mathcal{L}\left\{#1\right\}}


\addtolength{\topmargin}{-.875in}
\addtolength{\textheight}{1.75in}

\newcommand{\solution}[1]{
\begin{quote}\color{red}Solution:\quad 
\color{black} #1
\end{quote}
}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\ba}{\backslash}
\newcommand{\Zplus}{\Z^+}

\begin{document}
\title{Math 228: Homework 9}
\author{Mary Radcliffe}
\date{due 9 Dec 2016}
\maketitle

Complete the following problems. Fully justify each response. You need only turn in those problems marked with a (*).
\begin{enumerate}

\item (*) Let $G$ be a planar graph on $n$ vertices. Prove that the number of edges in $G$ is at most $3n-6$.

\item Let $G$ be a graph. Define a {\it block} of $G$ to be a subgraph of $G$ that is 2-connected, and has no cut-vertices; that is, a block is a subgraph such that removing any edge OR any vertex yields a connected graph.

\begin{enumerate}
\item Identify the blocks in the following graph by the vertices contained in each block. A vertex may appear in more than one block.
\begin{figure}[htp]
\hspace{.5in}\includegraphics[scale=.6]{blocks.pdf}
\end{figure}
\vspace{-2in}
\item Show that a graph is planar if and only if each of its blocks is planar. You may want to use induction on the number of blocks.
\end{enumerate}

\item (*) Suppose that $G$ is a 2-connected graph such that every vertex in $G$ has degree at least 3. Show that there exists an edge $uv\in E(G)$ such that $G\ba\{uv\}$ is also 2-connected.


\item (*) Complete problem 12.3.1 on page 195.

\item Complete problem 12.3.5 on page 195.

\item Complete problem 13.3.1 on page 204.

\item (*) Complete problem 13.3.4 on page 204.

\item An {\it independent set} in a graph $G$ is a set of vertices in $G$ that contain no edges of $G$. Show that coloring a graph with $k$ colors is the same as finding a partition of $V(G)$ into $k$ independent sets.

\item (*) Complete problem 13.4.4 on page 210. The graph constructed in this way is called the {\it line graph} of $K_5$, and certainly every graph could yield a line graph formed in the same way. 

\item (*) Complete problem 13.4.5 on page 210.

\end{enumerate}
\end{document}