\documentclass[11pt,leqno]{article}
\usepackage{graphicx}
\usepackage{fullpage}
\usepackage{enumerate}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{hyperref,cleveref}
\usepackage{multicol}
\usepackage{soul}
\usepackage{xcolor}
\usepackage{graphicx}                                          
\usepackage{float}                                                

\vfuzz2pt 
\hfuzz2pt 

\newtheorem{thm}{Theorem}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[thm]{Remark}
\newtheorem*{fact*}{Fact}
\numberwithin{equation}{section}

\newtheoremstyle{probstyle}  
{3ex}                        
{0pt}                        
{\normalfont}                
{-3ex}                       
{\normalfont\bfseries}       
{.}                          
{.5em}                       
{}                           
\theoremstyle{probstyle}
\newtheorem{problem}{Problem}

\newtheoremstyle{fthmstyle}  
{3ex}                        
{0pt}                        
{\normalfont\itshape}        
{0ex}                        
{\normalfont\bfseries}       
{.}                          
{.5em}                       
{}                           
\theoremstyle{fthmstyle}
\newtheorem{fthm}{False Theorem}

\newcommand{\abs}[1]{\left\vert#1\right\vert}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\R}{\mathbb R}
\newcommand{\eps}{\varepsilon}
\setlength\parindent{0pt}
\setul{.25ex}{}

\begin{document}
	\title{Math 154 Homework \#4\vspace{-3ex}}
\date{Spring 2023}
	\maketitle
	\begin{center}
		Due date: \textbf{11:59pm} Pacific Time on \textbf{Wed, May 3} (via \href{https://www.gradescope.com/}{Gradescope})
	\end{center} 
	\vskip 3ex
	\thispagestyle{empty}
	
	\noindent\emph{On the first page of your work, please write a list of everyone with whom you collaborated on this assignment, as well as any outside sources you consulted, apart from the textbook, your notes, and the course staff. If you did not collaborate with anyone, please explicitly write, “No collaborators.”}\\
	
	\begin{problem}   
		Answer \textbf{Question 3.4} at the end of Chapter 3 of the textbook.\\
		
		\textcolor{red}{You do \textbf{not} need to do the Dijkstra's algorithm part, but if you do it (correctly), you will receive 1 bonus point.} Dijkstra's algorithm is slightly beyond the scope of this course and we aren't going to cover it in lecture, but you'll see it again if you take CSE 100, so this problem is in case you want to get some practice with it now. Here is a video explaining Dijksta's algorithm (\url{https://youtu.be/EFg3u_E6eHU}), and you can also look at \textbf{Example 14} in the book.\\
		
		\textit{\textbf{Clarification:} For Prim's and Kruskal's Algorithms, \ul{specify the order in which the edges are added}. For Dijkstra's algorithm, you do not need to show every step, but you should show at least some work to demonstrate that you used Dijkstra's algorithm to solve the problem, rather than solving it by inspection. (For example, you could give the output of the first two iterations of the algorithm, or show a few of the intermediate paths you find while executing the algorithm.)  And (reprinted here for your convenience) this is the graph you should reference for this problem:}
		
		\begin{figure}[H]
			\centering
			\begin{minipage}{.35\textwidth}
				\includegraphics[width=1\linewidth]{./fig_3.6}
				
			\end{minipage}
		\end{figure}
		

	\end{problem}
	



	
\newpage
	\begin{problem}Consider the following false ``theorem" and proof.\\
		
	\hspace{.1\textwidth}\fbox{\begin{minipage}{.78\textwidth}
		\begin{fthm}\label{thm:false}
			Let $G$ be a graph on $n \geq 2$ vertices. If each vertex in $G$ has degree at least $1$, then $G$ is connected.
		\end{fthm}
		\begin{proof}[Proof of \Cref{thm:false}] We will proceed by induction on the number of vertices $n$.\\\vspace{-1ex}
			
			\textbf{Base step:} $n=2$. There are only 2 vertices, so if both have degree at least 1, then the graph must consist of a single edge; hence it is connected. \\\vspace{-1ex}
			
			\textbf{Inductive step:} 
			Let $G$ be any graph on $n$ vertices where every vertex has degree at least 1, and add a new vertex $v$ with degree at least 1 (to form a new graph $G'$ on $n+1$ vertices in which every vertex has degree at least 1). By the inductive hypothesis, $G$ is connected, and since $v$ has degree at least 1, it is connected to at least one vertex in $G$. 
			So all of $G'$ is connected. This completes the inductive step.
		\end{proof}
	\end{minipage}}
		\begin{enumerate}
			\item[\textbf{(a)}] Give a counterexample to \Cref{thm:false}
			
			\item[\textbf{(b)}] Identify the logical flaw in the proof above, and clearly explain why the logic is flawed.
			
			\textit{(Note: there may be more than one writing error or omission, but there is only one ``fatal flaw," and you must correctly identify it to get credit!)}\\
		\end{enumerate}
\end{problem}


\begin{problem}
	The \textbf{Hypercube Graph}\footnote{The Hypercube $Q_n$ is an important object of study in computer science, and independent sets in $Q_n$ are very closely related to \textit{error-correcting codes} (essentially, each independent set is an \textit{error-detecting code}). You can read more here: \url{https://plus.maths.org/content/error-correcting-codes} And if you're interested, please feel free to ask about this in office hours or on Piazza!} $Q_n$ is the graph whose vertex set is the set of all binary strings of length $n$, and where two vertices are adjacent if they differ in exactly one coordinate (for example, in $Q_3$, the vertex $001$ is adjacent to $011$, but not $100$). 
	\begin{enumerate}
		\item[\textbf{(a)}] Show that $Q_n$ is bipartite for all $n\geq 2$.
		\item[\textbf{(b)}] Show that $Q_n$ contains at least\ \ $2 \cdot \left(2^{2^{n-1}}\right)-1$\ \ independent sets, for all $n\geq 2$.\\ \textit{Note: you may use the following fact without proof: the number of binary strings of length $k$ and the number of subsets of a $k$-element set are both equal to $2^k$.}\\
	\end{enumerate}
\end{problem}


\begin{problem}\label{prob:leaves}   
	Answer \textbf{Question 5.15(a)} at the end of Chapter 5 of the textbook.\\ 
\end{problem}

			









	








	
	
\end{document} 