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.