## Math 154 Discrete Mathematics and Graph Theory Homework 5

This homework is due on gradescope by Friday November 5 th at $11: 59 \mathrm{pm}$ pacific time. Remember to justify your work even if the problem does not explicitly say so. Writing your solutions in IATEXis recommend though not required.
Please cite any other students with whom you collaborated on any problems.

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?

real analysis代写， MATH 184代写，实分析代写， 数学分析代写请认准UpriviateTA. UpriviateTA为您的留学生涯保驾护航。

# Math 154: Discrete Mathematics and Graph Theory

## Fall 2021

Announcements:

Homeworks:

Exams:

Other:

Categories: 图论数学代写