Homework #1
Section 2: 9. Take a connected component of G and let it have n vertices. The degrees of these vertices range from 1 to n-1 (n-1 numbers) and so values of the n vertices' degrees must repeat some value.
10. Left graph in Fig. 2.20 has a 5-cycle, right graph has a 5-cycle and a 6-cycle.
14. (i) equals degree of vertex, (ii) equals degree of vertex, (iii) equals 2.
Section 3: 1. Straightforward, 8.(i) since a graph and its complement together have all the edges of a complete graph, self-complementary graph on n vertices has 1/2 of the edges in Kn = n(n+1)/4. So 4 must divide n or n+1.
(ii) a 4-vertex (3-edge) path and a 5-cycle are self-compl. graphs with 4 and 5 vertices.
9. (i) and (ii) verify by drawing, (iii) if each edge is adjacent to k-1 other edges at each endvertex, 2(k-1) total.
Section 5: 1. By inspection, 5. (i) 2,2, (ii) 3,3, (iii) 4, 4 (iv) 4,4.
6. (i) Removing all the edges incident to one vertex is a disconnecting set. Thus there is a disconnecting set of size k (maybe another one is smaller). (ii) One example-Create two K5's and a vertex x adjacent to two vertices in each of the two K5's.

Homework #2
Section 12: 5. (ii) Kr,s,t is planar when two of the subscripts are 1 or all three are at most 2.
6. (ii) Contract the five 'radial' edges to get a K5.
7. (ii) Any disconnected graph with one component that is non-planar, e.g. a K5, cannot be contracted to a K3,3 or K5 . (A disconnected graph cannot be contracted to a connected graph.)
8.Two graphs are homeomorphic if there are isomorphic after the 'removal' of vertices of degree two. Then after the removal of these vertices, m - n is the same for the two graphs. If we undo the removal of vertices of degree 2-that is, add them back-this increases m and n each by one and so leaves m - n unchanged.
9. (i) K4 and K2,3 are seen to be non-outerplanar by drawing all but one of their vertices in an outerplanar fashion and then observing that the final vertex cannot be added in an outerplanar fashion.
(ii) If a subgraph is not outerplanar, then making a contraction or replacing a path by an edge in this subgraph will not create an outerplanar configuration. Thus if a subgraph is contractible or homeomorphic to K4 and K2,3 (which are non-outerplanar), then the subgraph must be non-outerplanar. Such the original whole graph was outerplanar, all subgraphs must be outerplanar and so none can be contractible or homeomorphic to K4 and K2,3.
Section 13: 13.1 Done by inspection 3(i) girth = 5 implies all bdy => 5. So 5f <= sum(bdy) = 2m --> m - n +2 = f =< (2/5)m --> (3/5)m - n + 2 <= 0 --> (3/5)m <= n - 2 --> m <= (5/3)(n-2).
(ii) Petersen graph has girth „ 5 and so part (I) applies. Petersen graph has m = 15 and n = 10 which does not satisfy the inequality in (i).

AMS 303 Homework #3
Section 13: 4.(i) polyhedral => deg => 3 --> 3n =< sum(deg) = 2m. Then m - f + 2 = n =< (2/3)m --> m <= 3f - 6. Let f = f5 + f6. (f5 = no. of 5-faces), then
(*) 5f5 + 6f6 = sum(bdy) = 2m.
Also m =< 3f - 6 = 3(f5 + f6) - 6 or
(**) 2m < = 6f5 + 6f6 - 12 Combining (*) and (**) yields 12 <= f5.
(ii) If deg = 3, then all the inequalilties in the preceding argument are equalities leading to 12 = f5.

5. As in previous problem, deg => 3 => 3n <= sum(deg) = 2m. Then m - f + 2 = n ¾ (2/3)m --> m <= 3f - 6. Assume all faces have bdy => 5 so that 5f <= sum(bdy) = 2m. But 2m ¾ 6f - 12. So 5f <= 6f - 12 or 12 ¾ f. Thus contradicts the given fact that f < 12.

6. Cubic --> deg = 3 and so 3n = sum(deg) = 2m. Then m - f + 2 = n = (2/3)m --> m = 3f - 6 and then 2m = 6f - 12. If fi is no. of faces with i bounding edges, then
(*) f = sum(fi) or 6f = sum(6fi) and (**) sum(bdy) = sum(i fi)
. Since sum(bdy) = 2m = 6f - 12, then using (*) and (**) we have sum(i fi).= 2m = sum(6fi) - 12. Collecting terms gives the required formula.

7. Assume G has 11 vertices. G and its complement G* together wil have C(11,2) = 55 edges. Since m =< 3n -6 in simple planar graphs, neither G nor G* can have more than 3(11) - 6 = 27 edges, or together more than 54 edges. Contradiction.

Section 15. 2. (ii) and 3. Results follow directly by drawing duals. 5. Verify as requested.
8. Three-connected means that at least three vertices must be removed to disconnect the graph. This implies that each vertex has degree => 3 ( if deg(x) =2, deleting x's two neighbors would disconnect x from the each of the graph). Then in the dual, the original constraint deg => 3 becomes bdy => 3 which implies the dual is simple.

AMS 303 Homework #4
Section 17: 1. 2, 4 4. (ii) 3, (iii) 2, 5.(i) 3 , (ii) 2 versus k (=>1).
7. Define C(x) = size of a color class containing a vertex x. Then C(x) <= n-d (since n-d counts x and all vertices not adjacent to x). Let C = largest size of a color class. Then also C <= n-d. But since every one of the n vertices in G must be in some color class, n <= X(G) C <= X(G)(n-d) or X(G) <= n/(n-d), as required.
8. (i) m <= 2n- 4 by Cor. 13.4,or 2m <= 4n - 8. If false, deg => 4 --> 4n <= sum(deg) = 2m <= 4n-8. Contradiction.
(ii) Prove is just like Thm 17.3 except we use 4 instead of 6 colors and max degree is 3 instead of 5.
Section 19: 1. B must be Yellow, 3. Many possibilities, e.g., a simple square (4-cycle).
4. This construction will yield vertices of even degree and so by Thm 19.1, graph is face 2-colorable.
7. By Exer. 13.5, G has a face of bdy <= 4. Easiest to prove dual version, if G (and all subgraphs) have a vertex of deg <= 4, show that graph is vertex 4-colorable. Use same argument as in Them 17.4.