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.