Math 510: Introduction to Graph Theory
Spring 2008

Additional Exercises

Index

Chapter 1 | Chapter 2 | Chapter 3 | Chapter 4 | Chapter 5 | Chapter 6 | Chapter 7 | Chapter 8 | Chapter 9 | Chapter 10 | Chapter 11 | Chapter 12
 
• Chapter 1
In these problems:
• H(G) is the oriented incidence matrix.
• n = |V|.
• c is the number of components of G.
• b is the number of bipartite components of G.
1. Prove: Lemma. In H(G), every minor has determinant equal to 0 or +1 or −1.
2. Prove: Theorem. The rank of H(G) equals n − c.
3. Let B be the unoriented incidence matrix. Prove: Theorem. Over a field F, the rank of B is equal to n − c if F has characteristic 2, and n − b if the characteristic is not 2. (N.B. This is properly viewed as a special case of the oriented incidence matrix generalized to signed graphs.)
4. If successful with #24, a research question is to generalize to signed graphs. The generalization should include Mader's Theorem 1.4.3 if possible.
5. For which graphs is the line graph L(G) regular?

• Chapter 2

With regard to the circuit packing theorem 2.3.2, here are two questions that seem interesting.
1. The bound f(k) given in the theorem is unlikely to be best possible. Let F(k) be the best possible bound. We know F ≤ f. Can you prove anything more about F? For instance, is F(k) ≤ 3k (log k + log log k + 4) or 4k (log k + log log k + 3) (just as indications of what one could ask)? On the other side, prove F(k) ≥ k. Is F(k) ≥ 2k? ck for some c > 1? I'm confident that this question has some results in the literature but is far from solved. Any work you do on any of these questions would make a fine homework problem.
2. The case k = 2 is quite interesting. F(2) is the smallest number of vertices that cover all circuits in every graph that has no two vertex-disjoint circuits. Our f(2) = 41, so F(2) ≤ 41, but the true value is certainly much smaller. What is that true value, or how close can you get to it? You might try doing it directly (I'd be happy with that as a homework exercise), or you might look up Lovász's theorem (see Bollobás, Extremal Graph Theory) to deduce the true value from it.
3. Does every cubic graph with exactly one isthmus have a perfect matching? (Thanks to Justin Almeida.)

4. Find the arboricity and the tree-packing number of the complete graphs, using the theorems of Section 2.4. (The tree-packing number is the largest number of edge-disjoint spanning trees.)
5. Prove that the book's definition of a stable marriage is almost impossible to satisfy, directly contrary to the theorem claimed in the book.
6. Petersen graph problems. Let P denote the Petersen graph; P − v is P with a vertex deleted. (We know from the symmetries that it doesn't matter which vertex you delete.)
   1. Does P have a perfect matching? (Of course.) How many? (Fun.)
   2. Is P − v factor critical?
   3. Find a set S for P as in the Gallai-Edmonds theorem 2.2.3. Use it to deduce (from the theorem) that P has a perfect matching.
   4. Does P have a Hamiltonian cycle? Does P − v have one?
   5. Does P − v have a Hamiltonian cycle? How does that help with a previous part of this question?
   6. What are the girth, diameter, and radius of P?
   7. What is the vertex cover number? (That's the smallest cardinality of a vertex cover.)
7. For each of the following graph families, decide which members have a 1-factor. Also, find the S of Theorem 2.2.3 that tells you so.
   1. The wheels Wⁿ = Cⁿ * K¹ (see page 59) for n ≥ 3.
   2. The complete graphs Kⁿ for n ≥ 1 (easy).
   3. The line graphs L(Kⁿ) for n ≥ 3.
   4. What does your answer for L(Kⁿ) mean, directly in terms of Kⁿ?
   5. The complements of line graphs, −L(Kⁿ), for n ≥ 3. (I use the minus sign because I can't do the overbar in HTML. If you know how, please let me know.)
   6. Interpret your answer for −L(Kⁿ) directly in terms of Kⁿ.
8. Apply the tree-packing and arboricity theorems (Section 2.4) to
   1. the complete graphs;
   2. the complete bipartite graphs.

• Chapter 3

1. The second proof of Menger's theorem does not prove the following statement:
   • If in a graph G, we have a set P of fewer than κ(A,B) disjoint A-B paths, then there is a set Q of |P| + 1 disjoint A-B paths such that V(Q) contains V(P).
   Question. Is this statement true? Can you prove it or find a counterexample?
2. Prove the following theorem, which is a perhaps more primitive version of Whitney's theorem 3.3.6(i). Theorem. If G is not complete, then the connectivity κ(G) = min{κ_G(x,y) : x, y nonadjacent vertices in G}.
3. Deduce Menger's Theorem (set version) 3.3.1 from Menger's Theorem (vertex version) 3.3.5(i).

• Chapter 4

1. Let G be a plane graph that is not 2-connected. Is it possible for every face boundary to be a circuit?
2. Prove that G is planar iff there is a simple basis of the cycle space that consists of circuits.
3. Let G be 2-connected. I claim that, for any simple basis of the cycle space that consists of circuits, the sum of the basis is a circuit and these circuits (the basis together with its sum) are the face boundaries in some planar embedding of G. Prove or disprove.
4. Show how to identify the circuits and bonds among all the members of the binary cycle and cocycle spaces of a graph.
5. Suppose H and H' are abstract duals of a graph G. Show that H and H' are 2-isomorphic, i.e., related by a sequence of Whitney 2-operations. (Whitney's 2-isomorphism theorem.)

• Chapter 5

1. Prove that every planar graph with girth at least 4 is 4-colorable (Simplified Grötzsch's Theorem).
2. Can you find a way to prove Grötzsch's Theorem by combining the ideas of the preceding problem and of the 5-Color Theorem (the proof in the book)?
3. Suppose G is the union of G' and G'' that have in common just a single vertex. Show that the chromatic function satisfies
   χ_G(k) = χ_G'(k) χ_G''(k) / k.
4. Prove the Great Big Lemma: The chromatic function (a.k.a. polynomial) satisifies
   χ_G(k) = χ_G-e(k) − χ_G/e(k) for k = 1,2,3,....
   
   (G is a multigraph and contraction is not simplified.)
5. Use the Great Big Lemma to prove the Great Big Theorem:
   1. (G.D. Birkhoff, 1912, for planar graphs; Whitney, 1930s, for all graphs) χ_G(k) is a polynomial function of k = 1,2,3,.... Furthermore, it is monic of degree n = |V|, its coefficients are integers alternating in sign (i.e., the coefficient of k^n-i has sign (−1)ⁱ), and the coefficient of k^n-1 is −|E| (for a simple graph). Exception: if G has a loop, then χ_G(k) = 0.
   2. (R.P. Stanley, 1973) The number of proper pairs (c,α) of a k-coloring c and an acyclic orientation α equals χ_G(k), for k = 1,2,3,....
   3. (R.P. Stanley, 1973) The number of compatible pairs (c,α) of a k-coloring c and an acyclic orientation α equals (−1)ⁿ χ_G(−k), for k = 1,2,3,....
   4. (R.P. Stanley, 1973) The number of acyclic orientations of G equals (−1)ⁿ χ_G(−1).
   Hint: To prove (b, c), use induction on |E| in combination with Lemmas 5.A and 5.B.
   • Lemma 5.A: The number p_G(k) of proper pairs of a k-coloring and an acyclic orientation satisfies
     p_G(k) = p_G-e(k) − p_G/e(k) for k = 1,2,3,....
   • Lemma 5.B: The number q_G(k) of compatible pairs of a k-coloring and an acyclic orientation satisfies
     q_G(k) = q_G-e(k) + q_G/e(k) for k = 1,2,3,....
6. Calculate χ_Cⁿ(k), the chromatic polynomial of the n-circle Cⁿ (for n ≥ 3, of course). This is a very good practice problem on computing chromatic polynomials.
7. Prove Lemma S1. The chromatic polynomial of a signed graph Σ is not changed by switching.
Warning: The following two problems depend on studying basic signed graph theory first. I'll be presenting that in class.
8. (a)   Prove Theorem S2. The chromatic polynomial χ_Σ(2k+1) and the zero-free chromatic polynomial χ_Σ*(2k) satisfy the deletion-contraction formula
     c_Σ = c_Σ-e - c_Σ/e,
   where c denotes χ(2k+1) or χ*(2k) and e is any link.
   (b)   Deduce that these so-called "polynomials" really are polynomial functions of their arguments and can therefore be extended to all real or complex-number arguments.
9. Prove Theorem S3. (−1)ⁿ χ_Σ(−1) equals a(Σ), the number of acyclic orientations of Σ. Hint: A useful lemma would be that a(Σ) satisfies the deletion-contraction recurrence.
10. The chromatic number of a surface is the largest chromatic number of any (simple) graph that embeds in that surface.
    1. Complete the proof that the chromatic number of the torus T₁ is 7 by showing that K⁷ embeds in the torus.
    2. Use Euler's polyhedral formula, as in class, to deduce an upper bound on the chromatic number of the g-fold torus T_g, that is, the sphere with g handles.
    3. To prove the upper bound is the exact number, what complete graph would you want to embed in T_g?
    4. See if you can embed that complete graph, for g = 2. (It gets very hard as g increases, but I think g = 2 is fun to try after getting g = 1, if you want a further challenge of that kind.)
11. There are a couple of questions about the proof of Brooks's Theorem.
    1. Fill in the details of the induction step, where you have to look at how the theorem applies to G − v.
    2. Diestel's (3) (my Lemma 1) says that C_ij is a v_i-v_j path. His (4) (my Lemma 2) says that any two such paths are internally disjoint. Question: Does the proof really need the second statement? If not, it can be shortened.

• Chapter 6

1. Prove Lemma. If f is a nowhere-zero k-flow on a graph G, then f restricted to any block G' is a nowhere-zero k-flow on G'.
2. Prove by analyzing the augmentation values ε of augmenting paths that a network with real capacities has a maximum flow, i.e., the supremum of values of flows is attained by a flow.

• Chapter 12

1. Prove Lemma. Let M be a minor-closed class of finite graphs, G \ M its complement, and F = Min(G \ M). Then a graph G is in M if and only if G has a minor that belongs to F.
2. Show that tw(Cⁿ) = 2. Deduce that tw(G) > 1 if G is not a forest.
3. Show that tw(Kⁿ) = n - 1.
4. Show that tw(Kⁿ \ e) = n - 2.
5. This question has three parts. The answer to (b) should be such that it makes (c) true.
   1. Here G is a tree. Take for T any spanning tree of the line graph L(G) and for V_t the vertex set of the edge t ε E(G). Prove this is a tree decomposition of G.
   2. Define a minimal tree decomposition (Exercise 12.13 might or might not be helpful here) of any graph G.
   3. Prove that every minimal tree decomposition of a tree G is obtained as in part (a).

6. Continuing Problem 12.6 (from the book):
   1. Prove that the finite trees of bounded diameter are well-quasi-ordered by the subgraph relation. (Bounded diameter means there is a number M such that you're only considering trees with diameter ≤ M. M could be any number.) Hint: Start with small values of M.
   2. Is the same true of finite trees with bounded maximum degree?

To my home page.