% ---------
%  Compile with “pdflatex hw0”.
% --------
%!TEX TS-program = pdflatex
%!TEX encoding = UTF-8 Unicode

\documentclass[11pt]{article}
\usepackage{jeffe,handout,graphicx,mathtools}
\usepackage[mathletters]{ucs}	% define text Greek letters; load BEFORE inputenc
\usepackage[utf8]{inputenc}	% Allow some non-ASCII Unicode in source
\usepackage{fourier-orns}
\usepackage{eucal,wasysym}

\usepackage{enumerate}
\usepackage{stmaryrd}

\hidesolutions

% ======================================================
\begin{document}

\headers{CS 473}{Homework 10 (due April 26)}{Spring 2016}
\thispagestyle{empty}

\begin{center}
\Large\textbf{CS 473 \,\decosix\,  Spring 2016}%
\\
\LARGE \textbf{\decothreeleft~ Homework 10 ~\decothreeright}
\\[0.5ex]
\large Due Tuesday, April 26, 2016, at 8pm
\end{center}

\hrule
\begin{center}
\textbf{\decofourleft~ This is the last graded homework of the semester. ~\decofourright}
\end{center}
\hrule
\bigskip

\begin{enumerate}
\parindent 1.5em \itemsep 3ex plus 0.1fil
%----------------------------------------------------------------------
\item
A \emph{double-Hamiltonian circuit} in an undirected graph $G$ is a closed walk that visits every vertex in $G$ exactly twice.  Prove that determining whether whether a given undirected graph contains a double-Hamiltonian circuit is {NP}-hard.


%----------------------------------------------------------------------
\item
A subset $S$ of vertices in an undirected graph $G$ is called \EMPH{triangle-free} if, for every triple of vertices $u,v,w\in S$, at least one of the three edges $uv,uw,vw$ is \emph{absent} from $G$.  Prove that finding the size of the largest triangle-free subset of vertices in a given undirected graph is {NP}-hard.

\begin{inline}
\includegraphics[scale=0.4]{../notes/Fig/triangle-free}\\
A triangle-free subset of 7 vertices.\\
This is \EMPH{not} the largest triangle-free subset in this graph.
\end{inline}


%----------------------------------------------------------------------
\item
Suppose you are given a magic black box that can determine \textbf{in polynomial time}, given an arbitrary graph $G$, whether $G$ is $3$-colorable.  Describe and analyze a \textbf{polynomial-time} algorithm that either computes a proper $3$-coloring of a given graph or correctly reports that no such coloring exists, using the magic black box as a subroutine.  \Hint{The input to the magic black box is a graph.  Just a graph.  Vertices and edges.  Nothing else.}



\end{enumerate}

\end{document}
