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.