        \problemdata       % Takes 5 *mandatory* arguments
        {planar-graphs}             % latex-friendly label for the prob.
        {graphs}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {S02 PS4-2} % Usage (list ones you are aware of).
        {Ashish, S02}        % Last revision info (author, date).


\begin{problem}

A planar graph is one which can be drawn in the plane without any
edges crossing (i.e. without the lines or arcs representing them
intersecting except at common endpoints).  Any planar graph with $n$
vertices and $m$ edges satisfies $m \leq 3n-6$.  Show that
\begin{problemparts}
\problempart any planar graph has a node of degree at most $5$.\\

\solution{Suppose that every vertex has degree at least $6$.  Then
\begin{eqnarray*}
2m&=&\sum_{v \in V}\textrm{deg}(v)\geq\sum_{v \in V}6=6n\\
m&\geq&3n
\end{eqnarray*}
contradicting our assertion that $m \leq 3n-6$.
}


\problempart any planar graph can be colored with six colors.

\solution{

The proof is by induction on the number of vertices $n$.

$P(n) = $ ``A planar graph of $n$ vertices can be colored with at most
$6$ colors''.

{\bf Base case:} $P(1)$ is true because a single vertex
 can be colored with $1$ color.

{\bf Inductive step:} 
Assume $P(n)$ is true in order to show that $P(n+1)$ is true.

Let $G$ be a planar graph with $n+1$ vertices and remove a vertex $v$ 
of degree 
$5$ (or less).  The remaining $n$-vertex graph can be colored with $6$ colors
by the inductive hypothesis.  Re-attach $v$.
$v$ is adjacent to at most $5$ vertices, occupying at most $5$ out of the
six colors.  We can use the remaining color to color $v$.

We have shown that $P(n) \rightarrow P(n+1)$, so the proof is complete.

}

\end{problemparts}
\end{problem}
