Problem 1. Question 1 (Block Structure of Trees, 20 points). Let $T$ be a finite tree. Show that $T$ is the block graph of some other tree $T^{\prime}$ 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 .

Problem 2.

Question 2 (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$.
(a) 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]
(b) 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]

Problem 3.

Question 3 (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.
(a) 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 or down and an integer number of units to the left or right. 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]
(b) 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]

Problem 4. Question 4 (Extra credit, 1 point). Approximately how much time did you spend on this homework?