\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

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

Lemma: any tree with $n$ vertices has $n-1$ edges:

Base case:  1 vertex, no edges

Inductive hypothesis: P(n):  for any tree of size $k \leq n$ there are $k-1$ 
edges.

Assume $P(n)$, show $P(n+1)$:

Given a tree with $n+1$ vertices, take away one edge.  We then have two subtrees
of size $n_a$ and $n_b$ with $n_a + n_b = n+1$ and $n_a, n_b \leq n$.  By the
inductive hypothesis, the subtrees have $n_a-1$ and $n_b-1$ edges each.
Since we took away one edge to form the subtrees, the total number of edges
for a tree of size $n+1$ is $n_a-1+n_b-1+1=(n+1)-1$.

\problem Hard to Break

{ \em
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?
}

For a graph to be 2-connected, each vertex must have at least degree 2. 
So the minimum  number of edges is  
$|E|=\sum_{i=1}^n(\frac{1}{2}$degree of vertex $i) = 2n/2=n$.

\problem Tournaments


{\em
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.

}
Proof by induction on the number of vertices:

Inductive Hypothesis:   A Tournament graph of size $n$ has a Directed 
Hamiltonian Path (DHP).

Base case: 2 vertices \\
Since for every two vertices, there is is one edge between them, then there
must be a DHP in the direction of that edge.

Assume the hypothesis is true for a graph with $n$ vertices, prove that it's true
for a graph of size $n+1$ vertices.

Let $G=(V,E), |V| = n+1$ be our tournament graph.  Create a new graph, $G'$
by removing the vertex $v$ from $G$.  So $G'=(V',E')$ where  $V' = V - \{v\}$
and $E' = $ \{ all edges in $E$ except those containing $v$\}. Note that $G'$ is
still a tournament graph since there are still edges going between all 
the remaining nodes.  Since $G'$ has $n$ nodes, by the inductive hypothesis 
it has a DHP.  


Assign numbers to the vertices according to their order in the path, starting
with $v_1$ and ending with  $v_n$.

Now, add $v$ to the DHP.  There are three cases:
\begin{itemize}
\item Case 1: $(v, v_1) \in E$ \\
Add $v$ to the beginning of the DHP.

\item Case 2: $(v_n, v) \in E$ \\
Add $v$ to the end of the DHP.

\item Case 3: $(v_1, v) \in E$ and $(v, v_n) \in E$ \\

Let $S =\{v_i \mid (v, v_i) \in E\}$.  We know that S is not empty because
$(v, v_n) \in E$, so by well-ordering there must be a minimum element, 
$v_k \in S$.  Since $v_1 \notin S$, $(v_{k-1}, v) \in E$.  Therefore we
can insert vertex $v$ between vertices $v_{k-1}$ and $v_k$ thus  creating
a DHP of size $n+1$.

\end{itemize}







\end{problems}

\end{document}

