```

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):

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.

```