\documentclass{article}
\usepackage{amsthm, amssymb, amsmath,verbatim}
\usepackage[margin=1in]{geometry}
\usepackage{enumerate}
\usepackage{graphicx}

\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\N}{\mathbb{N}}



\newtheorem*{claim}{Claim}
\newtheorem{ques}{Question}


\title{Math 154 Homework 2}
\date{Fall 2021}

\begin{document}

\maketitle

This homework is due on gradescope by Friday October 8th at 11:59pm pacific time. Remember to justify your work even if the problem does not explicitly say so. Writing your solutions in \LaTeX is recommend though not required.

Please cite any other students with whom you collaborated on any problems.

\begin{ques}[Non-Multiple of 3 Cycles and Circuits, 25 points]
Prove that if a graph $G$ has a closed walk whose number of edges is not a multiple of $3$ then by removing edges from this walk, one can find a cycle whose number of edges is not a multiple of $3$.
\end{ques}

\begin{ques}[Distances and BFS, 25 points]
In a graph $G$ define the \emph{distance} between two vertices $u$ and $v$ to be the smallest number of edges in any path from $u$ to $v$ (or $\infty$ if no such path exists). Let $G$ be a connected graph with a vertex $v$ and let $T$ be the breadth first search tree rooted at $u$. Prove that for every other vertex $v$ in $G$ that the distance from $u$ to $v$ equals the length of the unique path from $u$ to $v$ in $T$. (In other words the path from $u$ to $v$ in $T$ is a shortest path in $G$.)
\end{ques}

\begin{ques}[Bridges and Trees, 25 points]
Let $G$ be a connected graph. We call an edge $e$ of $G$ a \emph{bridge} if removing $e$ causes $G$ to become disconnected.

Prove that an edge $e$ of $G$ is a bridge if and only if $e$ is part of every spanning tree of $G$.
\end{ques}

\begin{ques}[Number of Bipartite Colorings, 25 points]
Let $G$ be a finite, bipartite graph with $C$ connected components. How many ways can the vertices of $G$ be colored black and white so that each edge of $G$ connects a black vertex to a white vertex?
\end{ques}

\begin{ques}[Extra credit, 1 point]
Approximately how much time did you spend on this homework?
\end{ques}

\end{document} 