Math6014 Assignments Georgia Tech Fall 2009 Please do all problems inDiestelthat are marked with "-" (however these problems will not be collected for grading). For each assignment, you must use only those results we have learned up to that assignment. Your work needs to be typewritten, and papers need to be stapled together (upper-left corner).Homework 1 (due Friday, Sept. 4): Read Chapter 1. 1. Let G be an r-regular graph. Show that G is bipartite iff it can be decomposed into copies of K_{1,r} (star with r+1 vertices). 2. Let G be a triangle-free graph with n (positive) vertices and m edges. Prove that there is a vertex x in G such that G-x-N(x) has at most m-4m^2/n^2 edges. 3. Prove that if G is a 2-connected graph with at least four vertices, then there is an edge of G such that G/e is 2-connected. Use this fact and induction to show that in a 2-connected graph any two vertices are contained in a cycle. 4. Let F be a finite field with p elements and consider the vector space F^3. Define the graph G as follows. The vertices of G are the 1-dimensional subpaces of F^3, and two vertices are adjacent in G iff they are orthogonal in F^3. Let A denote the adjacency matrix of G, with (A)_{ii} corresponding to the number of loops at vertex i. Find A^2, and find the eigenvalues of A. Homework 2 (due Friday, September 18): 1. Prove that if T is a tree and for every vertex v of T, q(T-v)=1, then T contains a perfect matching. 2. Let r be a positive integer. Suppose G is r-regular, and for every subset S of V(G) with |S| odd, there are at least r edges from S to V(G)-S. Show that G has a perfect matching. 3. Let G be a connected graph with minimum degree at least 3 and girth at least 4, and assume that G contains no vertex disjoint cycles. Prove that G is the complete bipartite graph K_{3,t}. 4. In the last problem, what happens when "girth at least 4" is replaced by "girth at least 3", i.e. can you characterize such G? Homework 3 (due Friday, October 9): 1. Show that every 3-connected graph with at least five vertices contains two independent contractible edges. 2. Use Problem 1 and induction to show that every edge in a 3-connected graph is contained in at least two induced nonseparating cycles. 3. Show that if G is a k-connected graph and has girth at least 4 then G has an edge e such that G/e is still k-connected. 4. Prove that every 4-connected graph containing a subdivision of $K_5$ is 2-linked. Homework 4 (due October 30): 1. Let G be a connected plane graph and let G* denote the dual graph of G. Prove that G contains a Hamilton cycle (a cycle through all vertices of G) iff V(G*) can be partitioned into two sets each inducing a tree in G*. 2. For a multigraph G, define F(G):=max{2|E(U)|/(|V(U)|-1): for all induced subgraphs U of G with |V(U)| odd and at least 3}. Show that the chromatic index of G is at least F(G). Moreover, if G is simple then F(G)-1 is at most the maximum degree of G. 3. Let S denote the collection of all graphs that can be constructed recursively from the odd wheels (one vertex joined to all vertices of an odd cycle) by applying the Hajos construction that involves two graphs and by always involving edges that are incident with the unique vertex of degree more than 3 (or any vertex if any of the graphs involved is a $K_4$). Prove the following statement: If G is not 3-colorable and has at most one vertex of degree more than 3, then G contains a subgraph that belongs to S. (Hint: Consider a minimum counterexample.) Homework 5 (due November 20): 1. Prove that if a graph contains a cycle through all vertices (i.e., Hamilton cycle) then it admits a 4-flow. 2. Show that if every 2-edge-connected cubic graph admits a 5-flow then every 2-edge-connected graph admits a 5-flow. 3. Let $G$ be a simple graph on n vertices and at least n^2/4+2 edges. Show that G contains a two triangles sharing exactly one vertex. Homework 6 (due December 4): Suppose any K_r-free graph can be made bipartite by deleting at most c(r)n^2 edges where c(r) only depends on r. Let H be any fixed r-chromatic graph. Then any H-free graph G can be made bipartite by removing at most (1+o(1))c(r)n^2 edges.