SOLUTIONS TO HW 5

2. (a) Vertices: A, B, C, D; Edges: AB, AC, AD, BD; deg(A)=3, deg(B)=2, deg(C)=1, deg(D)=2.

(b) Vertices: A, B, C; Edges: none; deg(A)=0, deg(B)=0, deg(C)=0.

(c)Vertices: V, W, X, Y, Z; Edges: XX, XY, XZ, ZV, XW, WY, YZ; deg(V)=1, deg(W)=2, deg(X)=6, deg(Y)=3, deg(Z)=2

7. (a) Could be a square with a vertex at each corner.

(b) Maybe something like a 6 sided wheel.

11. (a) C,B,A,H,F

(b) C,B,D,A,H,F

(c) C,B,A,H,F

(d) C,D,B,A,H,G,G,F

(e) 4(C,B,A; C,D,A; C,B,D,A; C,D,B,A0

(f) 3(H,F; H,G,F; H,G,G,F)

(g) 12 (Any One of the paths in (e) followed by any in (f).)

21. N connects to B with 2 edges, and once to C; A and C both connect once with B and once with S.

24. (a) Has a Euler circuit because all vertices are even degree.

(b) Has no Euler circuit, but does have a path because there are only 2 vertices with odd degree.

(c) Neither Euler path nor circuit because there are 4 vertices with odd degree.

30. Start on one of the inner most vertices. Cover the edges of the inner ring and then move outward and go around...finish with the outer most points.

33. Start by covering the left side of the graph.

37. (a) Neither, because there are more than 2 vertices of odd degree.

(b) Ask me if you can't find a path...

(c) Ditto.

42.

(a)You need to add 7 edges to the graph.

(b)Add 3 edges, going along the edges between the lower left and upper right vertices.

60. Yes, it is possible to walk over each bridge only once, but it will be a path, not a circuit. Start at either N or C and end at the other one.

71. Each component of the graph can be considered as a graph all by itself. So, according to Euler's Theorem 3, the number of odd vertices of odd degree (in each component) must be even. Therefore the 2 vertices of odd degree must be in the same component.