Solutions 12. 8.9: 22: Since b has odd degree, no Euler circuit, directed or not can exist. If there is a directed Euler path, it must go from c to b. Fleury's algorithm gives (for example) c,b,c,e,b,f,a,f,d,e,f,e,a,b,d,c,b. 28: a) Whenever m and n are even and positive. In that case K_(m,n) is connected, simple, and all vertices have even degree. b) To have an Euler path, all but 2 vertices must have even degree. That leaves as possibilities m=2 and n=any odd positive number. 30. No Hamilton circuit can exist because in any potential Hamilton circuit the edge cf would have to be traversed twice. 34. In any Hamilton circuit the edges ad and ab must be present. Repeating this thought for all outer corners, a Hamilton circuit must contain all of the edges that form the outer square. However, to get from the outer square to the inner points, one must also use at least one of the edges bj, hq, fm, do. But then at least one of the vertices b, h, f, o has all 3 adjacent edges participate in the Hamilton circuit. That is not possible since it would force that particular vertex to be traversed at least twice. Hence, there is no Hamilton circuit. 42: Yes. a,b,d,c,e. 62: As we know, a graph is bipartite if and only if it can be 2-colored. The graph of legal knight moves on _any_ chess board (square, rectangular or of any other shape) is obviously 2-colorable -- it is even already colored!!! (Black and white, as the chessborad is. Since a knight moves 2 in one direction and 1 in the other, it always moves from black to white and conversely. So black vertices only connect to white ones and white ones only to black ones.)