\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 5}
\date{Fall 2021}

\begin{document}

\maketitle

This homework is due on gradescope by Friday November 5th 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}[Block Structure of Trees, 20 points]
Let $T$ be a finite tree. Show that $T$ is the block graph of some other tree $T'$ if and only if the following condition holds: $T$ is a bipartite graph where all of the leaves are in the same part and the vertices in that part all have degree $1$ or $2$.
\end{ques}

\begin{ques}[Distinct Paths in a Block, 40 points]
Let $G$ be a finite graph that consists of a single block with more than $2$ vertices. Let $v$ and $w$ be two different vertices of $G$.
\begin{enumerate}[(a)]
\item Show that for any two distinct vertices $s$ and $t$ it is either possible to find an $s-v$ path and a $t-w$ path that do not share any vertices or it is possible to find a $t-v$ path and an $s-w$ path that do not share any vertices. [20 points]
\item Show that if $G$ has $m$ edges and $n$ vertices that there are at least $m-n+2$ different paths from $v$ to $w$. Hint: Use induction on the number of ears in an ear decomposition of $G$. [20 points]
\end{enumerate}
\end{ques}

\begin{ques}[Euler's Formula and Regular Tessellations, 40 points]
Let $G$ be an infinite graph with a planar embedding. Say that the embedding is periodic if translating all of the edges and vertices one unit up or to the left yields the same collection of edges and vertices. Say that the embedding is locally finite if any disk intersects only finitely many edges and vertices.
\begin{enumerate}[(a)]
\item For $G$ a locally finite, periodic planar graph, say that two vertices are equivalent if you can obtain one from the other by translating it an integer number of units up and an integer number of units to the left. Let $v$ be the number of equivalence classes of vertices. Similarly, let $e$ and $f$ be the number of equivalence classes of edges and faces of $G$. Prove that $v-e+f = 0$. [20 points]
\item Suppose that such a graph $G$ is $d$-regular and has exactly $s$ sides per face. What are all possible values of $d$ and $s$ for which this can happen? [20 points]
\end{enumerate}
\end{ques}



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

\end{document} 