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.)