\documentstyle[12pt,twoside,amsfonts,amstex]{article}
\input{macros-course-tutorials}

\parskip1.5ex
\parindent0pt

\begin{document}

\tutorial{tutorial8}{Problems for Tutorial 8}{April 7, 1997}

\begin{problems}

\problem Lost In the Forest

Consider a forest with $k$ connected components and $n$ vertices.  How many 
edges are in the forest?

\problem Hard to Break

A {\em 2-connected graph} is a graph in which $2$ edges must be removed to 
disconnect it.  What is the minimum number of edges that a 2-connected graph
of $n$ vertices must have?

\problem Tournaments

A {\em Tournament Graph} is a directed graph such that if
$u$ and $v$ are vertices then either $(u,v)$ is an edge or $(v,u)$ is
an edge but not both. A {\em Directed Hamiltonian Path} is a simple
path in a directed graph that contains every vertex exactly once. 
Prove by induction on the number of vertices that every tournament
graph has a directed Hamiltonian path.




\end{problems}

\end{document}

