Solutions 12 
--------------------

9.7: 

5: no, it's version of K(3,3).

6: yes. push the af-edge up. and the cd-edge down.

7: yes, but hard to explain.

8: no. there are no triangles, so the shortest circuit has length 4. 
   but the inequality e < 2v-3 is violated.

20: For homeomorphic graphs one can disregard vertices of degree 2
    (forget the vertex was ever there, but keep the edges). If you do
    that here, you get a graph with 4 vertices only: a,b,g,h. So this
    cannot be homeomorphic to K(3,3).

24: No because obviously there is a K(5) sitting inside the graph.

30: If you decompose K(3,3) into any pair of nonempty graphs A and B
    (so the vertices of A and B are those of K(3,3), the union of
    their edges make the edges of K(3,3), and A and B have no edges in
    common), then both A and B are planar. (Example: let A be one
    arbitrary edge of K(3,3) and let B be the rest.) It follows that
    the thickness of K(3,3) is no more than 2.
 
    On the other hand, the thickness cannot be 1 (that would say
    K(3,3) itself is planar, which we know is wrong), or zero (K(3,3)
    is not empty).Hence the thickness must be 2.

32: I will write ^ for "less or equal".  By Corollary 1, connected
    planar simple graphs with at least 3 vertices have e ^ 3v-6. If
    you have any planar simple graph with at least 3 vertices you can
    make it planar simple connected by adding edges. So after you
    added, e ^ 3v-6, and in particular (since you added edges) e ^
    3v-6 before you added them as well.
 
    Now Let G be connected simple. If G has 2 vertices or less, the
    inequality we are supposed to show is stupid, so we assume we have
    at least 3 vertices

    Let t be the thickness of G, so there is a way of taking t
    subgraphs A_1,...,A_t such that each A_i is simple, any 2 of the
    A_i have no edge in common, and their union is G. Note in
    particular that v(A_i), the number of vertices of A_i, is
    precisely v(G), for all i. Also, e(G), the number of edges of G,
    is exactly the sum of all e(A_i).

    Since each A_i fits the conditions of Corollary 1 (or the
    improvement we recorded in the first paragraph), e(A_i) ^
    3v(A_i)-6. If you add all these inequalities, (and there are t of
    them!) then you get e(G) ^ t[3v(G)-6]. And that is exactly what we
    were supposed to show.