HW 7 Solutions |
Ch. 5: 53-55, 57.
A1. Suppose a graph has a non-closed Euler path. Let v and
w be the first and last vertices of the path. As we travel along the path, every
vertex other than v and w that we visit, we immediately leave it. So, with each
visit, we trace two edges of that vertex, one as we reach the vertex, one as we
leave it. Thus every vertex other than v and w has an even number of edges.
Now we explain why each of v and w has odd degree. We start the path at v; this
traces one edge of v. From then on, every time we visit v, we also exit it, so
on each visit we trace two more edges of v. Thus v has an odd number of edges.
The explanation for w is similar: every time we visit w, we trace two edges of
w, except that the last time we visit w we don't leave it, so we trace only one
edge of w on the last visit. So w has odd degree.