Math6014 Assignments

                                Georgia Tech

                                Fall 2009


           
Please do all problems in  Diestel  that 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.