\documentclass{article}
\usepackage[top=1in,bottom=1in,left=1in,right=1in]{geometry}
\usepackage{fancyheadings,enumerate,xspace,amssymb}
\pagestyle{fancy}
%\usepackage{cs5114}
% macros useful for handouts and homeworks.
\newcommand{\setcourse}[1]{\newcommand{\course}{#1\xspace}}
\newcommand{\setsem}[1]{\newcommand{\sem}{#1\xspace}}
\newcommand{\setyear}[1]{\newcommand{\myyear}{#1\xspace}}
\newcommand{\sethwnum}[1]{\newcommand{\hwnum}{#1\xspace}}
\setcourse{CS 4104}
\setyear{2017}
\setsem{Spring}
\sethwnum{2}
\chead{\course (\sem \myyear): Homework \hwnum}
\newcommand{\reals}{\ensuremath{\mathbb{R}}}
\newcommand{\solution}[1]{\textbf{Solution:} #1}
\newcommand{\cut}[1]{\ensuremath{\mathnormal{}{cut}(#1)}}
\newcommand{\calg}{\ensuremath{{\cal G}}\xspace}
\newcommand{\calo}{\ensuremath{{\cal O}}\xspace}
\begin{document}
\title{\vspace{-0.5in}\textbf{Homework \hwnum}}
\author{\course (\sem \myyear)}
\date{Assigned on Wednesday, February 8, \myyear. \\Submit a PDF file
containing your solutions on Canvas by the beginning of class on
Wednesday, February 15, \myyear.}
\maketitle
\input{instructions}
\begin{description}
\item[Problem 1] (25 points) This problem is in three parts.
\begin{enumerate}
\item (10 points) If $G$ is an undirected graph and $v$ is a node in $G$, let us
use $G - \{v\}$ to denote the graph formed by deleting $v$ and all
its incident edges from $G$. In general, even if $G$ is connected,
it is possible that $G - \{v\}$ may contain two or more
connected components, e.g., if $G$ is a tree and $v$ is a node with
degree greater than one. However, this fragmentation cannot happen for
every node $v$. Prove this fact, i.e., prove that in every
connected, undirected graph $G$, there is at least one node $v$ such
that the graph $G - \{v\}$ is connected. \emph{Hint:} In the special
case that $G$ is a tree, any leaf can serve as $v$. How will you
find a ``leaf'' in a general undirected graph?
\item (10 points) Now prove that if $G$ is an undirected, connected graph on $n$
nodes that $G$ must contain at least $n-1$ edges. \emph{Hint:} Use
the statement in part (a) in combination with a proof technique we
used in class.
\item (5 points) Finally, prove that if $G$ is an undirected,
connected graph on $n$ nodes
that contains exactly $n-1$ edges, then $G$ does not contain a
cycle. \emph{Hint:} The statement you proved in part (b) may be helpful. \emph{Note:} We discussed this claim in class but I asked
you to prove it yourself. Now is your chance to do so!
\end{enumerate}
% \solution{
% }
\item[Problem 2] (25 points) Solve exercise 5 in Chapter 3 (page 108) of your
textbook. A binary tree is a rooted tree in which each node has at most
two children. Show by induction that in any binary tree, the number of
nodes with two children is exactly one less than the number of leaves.
To get started, given a binary tree $T$, let us define two useful quantities: $c_{T}$ ($c$
with $T$ as a subscript) the number of nodes in $T$ with two children, and
$l_{T}$ ($l$ with $T$ as a subscript) the number of leaves in $T$. With these
two quantities defined, the goal of the problem is to prove that for every tree
$T$, $c_{T} = l_{T} - 1$. To assist you with the proof, here are three
candidates for the induction hypothesis. In your solution, state which
candidate is correct and then provide the complete proof by induction based on
this choice.
\begin{enumerate}[(i)]
\item There exists a tree $T$ on $n - 1$ nodes such that $c_{T} = l_{T} - 1$.
\item For every integer $k$ between $1$ and $n - 1$, there exists a tree $T$
on $k$ nodes such that $c_{T} = l_{T} - 1$.
\item For every tree $T$ on $n - 1$ nodes, $c_{T} = l_{T} - 1$.
\end{enumerate}
% \solution{
% }
\item[Problem 3] (20 points) Solve exercise 7 in Chapter 3 (page 108-109) of
your textbook. I provide the essential part of the problem here.
\begin{quote}
\emph{Claim: Let $G$ be an undirected graph on $n$ nodes, where $n$ is an
even number. If every node of $G$ has degree at least $n/2$, then $G$
is connected.}
\end{quote}
Decide whether you think the claim is true or false, and give a proof of
either the claim or its negation.
% \solution{
% }
\item[Problem 4] (30 points) Solve exercise 9 in Chapter 3 (page 110) of your
textbook. Suppose that an $n$-node undirected graph $G$ contains two
nodes $s$ and $t$ such that the distance between $s$ and $t$ is strictly
greater than $n/2$. Show that $G$ must contain some node $v$, not equal
to $s$ or $t$, such that deleting $v$ from the graph destroys all
$s$-$t$ paths. (In other words, the graph obtained from $G$ by deleting
$v$ contains no path from $s$ to $t$.) Give an algorithm with running
time $O(m + n)$ to find such a node $v$. \emph{Hint:} Many of the layers in the BFS tree rooted at $s$ have a
special property.
% \solution{
% }
\end{description}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: