57. A graph G represents a street network to be traveled by a postal worker on foot, who must deliver mail to the houses on both sides of each street. How does one obtain from G a new graph H that represents the sidewalks that must be traversed? Does graph H always have an Euler circuit? Explain your answer.
57.
For each edge e of G, add another edge joining the vertices that are endpoints of e to obtain H. If G is connected, H does have an Euler circuit because whatever the valences of G, graph H has valences that are doubles of these and remains connected. Hence, H is even-valent and connected.