\documentclass[12pt]{exam}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{hyperref}
\usepackage{graphicx}
\newcommand{\ppp}{\par \noindent}
\newcommand{\R}{\mathbb{R}}
\newcommand{\ds}{\displaystyle}
\newcommand{\PS}{\mathcal{P}}
\pagestyle{empty}
\begin{document}
\centerline{\textbf{Deceptively Uninspiring Homework 8}}
\centerline{Due Wednesday May 28th at the beginning of class}
\bigskip
You may handwrite or type your answers/solutions/proofs. I highly encourage the use of a mathematical typesetting language (like \LaTeX). If you handwrite, please make sure that your work is legible, and please staple your homework when you turn them in.
\begin{questions}
\question A labeled graph is a graph where the vertices are labeled $1, \ldots, n$. As with labeled tournaments, the labels matter, but where each vertex is drawn does not. So the first two graphs are the same, but the third one is different.
\begin{center}
\includegraphics[scale=0.8]{labeledgraphs.png}
\end{center}
Prove that the number of labeled (simple, i.e., no double edges or loops from one vertex to itself) graphs on $n$ vertices is the same as the number of labeled tournaments on $n$ vertices.
\question Find an Eulerian cycle in the graph below by using the algorithm seen in class. Show your steps.
\begin{center}
\includegraphics[scale=0.8]{euleriancycle.png}
\end{center}
\question A \emph{forest} is a graph in which every connected component is a tree. Prove that the number of edges in a forest is $n$ minus the number of connected components.
\question \begin{parts}
\part You decide to go riding a century with your bike for the first time. Afraid that you will starve, you decide to bring not one, not two, but THREE Clif bars, one in each of your jersey back pockets. You like variety, so you want to bring along three different flavors of Clif bars among the 19 equally delicious flavors that exist. What is the probability that you bring a brownie bar, a macadamia bar and a peanut butter bar if the likelihood of picking any flavor is equal? Explain carefully every part of the formula that you come up with.
\part You will first eat the Clif bar in your left pocket, then the one in your middle pocket and finish with the one in your right pocket. Being a Clif bar connoisseur, you actually feel that eating first a brownie bar, then a macadamia bar and finally a peanut butter bar has nothing to do with first eating a brownie bar, then a peanut butter bar and finally a macadamia bar. As a Clif bar snob, how many different Clif bar tasting menus can you create for your ride? Again, explain in minute detail every part of the formula that you come up with.
\part As much as you love Clif bars, you must admit that you also like Kind bars and that they somehow feel a bit healthier. For your upcoming usual 50 mile ride, you know that a Clif bar and a Kind bar will suffice. Given that there are 29 different varieties of Kind bars, how many Clif bar/Kind bar duos exist? Again, explain your answer fully.
\part An even hungrier friend decides to go on the century with you and wants to bring 4 bars, Kind or Clif. This person being much more normal than you, they don't care whether some of the bars are the same (or even all of the same) nor how many are Clif and how many are Kind. How many different assortments of bars are there for this philistine? Your answer should be as whole as a whole wheat bar---which neither Clif or Kind offers, that would be gross.
\part Despite being abashed by the lack of discernment of your friend when it comes to snack bars, you appreciate the fact that they are willing to go ride 100km with you---and mostly that they put up with you, period. You offer to bring three Clif bars for them, and strongly advise them to buy a Kind bar as their final bar to have a balanced bar offering. In this case, how many different assortments of bars exist for your friend? Be at least as clear as the translucent packaging of Kind bars.
\end{parts}
\end{questions}
\end{document}