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