Math 381 Homework
Spring 2013

Good Advice and General Instructions on Homework Problems and Solutions

Due Wed., 1/30:
Do ## A1, A2, A4 for G = G₁ (do this first) and G₂, G₄.
Also, read Section 1.1.
Also, read the course information page and the homework instructions.

Due Fri. 2/1:
      # A3 (again, do G₁ first).

Hand in Wed. 1/30:
      ## A1–A4 for G₃.

Problem Set A

Some terminology about a graph (from the announcements page):

• Order: the number of vertices.
• Size: the number of edges.
• Separating set: a set of vertices whose removal leaves a disconnected graph.
• Disconnecting set: a set of edges whose removal leaves a disconnected graph.

A1. (a) Find a separating set. (b) Find one that is smallest.

A2. (a) Find a disconnecting set. (b) Find one that is smallest.

A3. Write down the degree sequence of G = G₁, G₂, G₃. (Omit G₄.)

A4. Treat G as a graph in which the vertices stand for people and the edges join pairs who don't get along together, so they can't be on the same committee. What is the largest possible committee?

Homework Set II (1/28)

Homework Set III (2/4)

For Tues. 2/5: Read Section 1.3.
Remember to check the announcements page for corrections to the textbook.

Do for discussion Tues. 2/5:
      Sect. 1.1, ## 1, 2, 4(a-c), 6.
      Sect. 1.2, # 1, 4, 7.

Do for discussion Wed. 2/6:
      Sect. 1.1, # 9.
      Sect. 1.2, ## 2, 3, 6, 8.
      # C2.

Hand in Fri. 2/8:
      Sect. 1.1, ## 3, 4(d), 5, 7, 8.
      Sect. 1.2, # 5.
      ## C1, C3.

Problem Set C

C1. This concerns Theorem 1.1.2 and the example G₀. I follow the book's notation. The sequence
      (S1) (4, 4, 4, 3, 3, 3, 2, 2, 1)
is known to be graphic, because it is the degree sequence of G₀. From (S1) the rule of Theorem 1.1.2 gives
      (S2) (3,3,2,2,3,2,2,1),
which, when rearranged in descending order, is
      (S3) (3,3,3,2,2,2,2,1).

1. In this example what are s, t₁, ..., t_s, n, d₁, ..., d_n? (Give their values.)
2. Label the vertices of G₀ by S, T₁, ..., T_s, D₁, ..., D_n as in the proof of the theorem.) Do this problem for each of the three possible choices of S.
3. If you delete vertex S, does the new graph G₀ − S have (S3) as its degree sequence?
4. Use the method in the proof to modify G₀ so that, when you delete S, you do get (S3) as the degree sequence of the new graph.

C2. In the graph F of Figure 1.1.16:

1. Find a longest path P. (Call its endpoints x and y.)
2. Pick an edge e of P which lies in a cycle of F. In F − e, find a path connecting x and y.
3. Pick an edge f of P which does not lie in a cycle of F. In F − f , is there a path connecting x and y?

C3. Let G be a graph which has a cycle. Let C be a cycle in G. Let a, b be arbitrary vertices in G, and let e be any edge in C. Explain in detail why, if G has a path connecting a to b, so does G − e.

Homework Set IV (2/4)

Hand in Fri. 2/15:
      Sect. 2.1, ## 5, 7, 15(a), 19, 20 (see announcement), and 9-10 (for I).
      ## D2, D5.

• The definition of a cycle on p. 16 is valid for n ≥ 3 but not for n = 1 or 2.
• In the proof of Theorem 1.3.5, at the top of p. 20, insert the sentence: "Then follow P₂ back to v₁." before "Then we have a cycle."
• In Exercise 2.1 # 4, you should find
    (a) any critical subgraph;
    (b) a critical subgraph whose chromatic number equals that of the whole graph.
• The graph I in Figure 1.2.5 is the one without a label. (It's the icosahedral graph.)

Always remember to check the announcements page for corrections!

Problem Set D

D1. Suppose G is a connected graph whose average degree is > 2.
  (a) Prove that G contains at least 2 cycles.
  (b) Prove that it is possible for G to have exactly 2 cycles.

D2. Suppose G is a connected graph whose average degree is 3.
  (a) Show that G has at least 4 cycles.
  (b) Is 4 the best possible number? Or can you prove that G must have 5 or more cycles? 6 or more?

D3. Find the chromatic number χ(G) where G is the graph in Figure 2.1.5.

D4. Is the graph of Figure 2.1.5 critical? Prove. (Don't believe everything you read!)

D5. Is the graph of Figure 2.1.6 critical? Prove.

Homework Set V (2/16)

• Theorem 2.2.4 is valid only for n ≥ 2.
• See the corrections for an addition to the explanation of components of a graph.

Problem Set E

E1. Prove there is no 1-factor in the graph of Figure 2.2.6 (a) left, (b) right.

E2. Is the graph of Figure 2.1.2 critical? Prove.

The first example graph theorists look at when they have a complicated new idea is K_p. The next one could be K_p − edge.

E3. Let G = K_p − edge. Find the chromatic number χ(G).

E4. Let G = K_p − edge. Find the edge chromatic number χ'(G) when p is even, i.e., p = 2n (n ≥ 1).

E5. Let V(K_2n) = {0, 1, 2, ..., 2n−2, x}. We have a standard way to decompose K_2n into 1-factors (see Section 2.2). In K₈, which "standard" 1-factor contains the following edge? (For your answer you may list all edges that belong to the 1-factor.)
  (a) 23.
  (b) 2x.
  (c) 36.
  (d) 15.

E6. Prove that, if G is a tree, then its edge chromatic number χ'(G) equals its maximum degree Δ(G).

E7. Find a Hamilton cycle or prove there is none.
  (a) Figure 2.3.4.
  (b) Figure 2.3.5. (Hint: there isn't!)
  (c) Figure 2.1.6.
  (d) Figure 2.3.7.

Homework Set VI (2/24)

• The last line on p. 38 (the one for (C_n)) should read
        n-1, n-2, n, n-3, n+1, n-4, ..., 2n-2, 2n-1, x.
  (This is equivalent to the printed line, but the printed line doesn't follow the pattern it's supposed to.)
• See the corrections for Section 3.1.

Problem Set F

F1. Let V(K_2n+1) = {0, 1, 2, ..., 2n-1, x}. We have a standard way of decomposing K_2n+1 into Hamilton cycles (see Section 2.3). In K₁₁, which "standard" Hamilton cycle contains the edge
  (a) 23 ?
  (b) 3x ?
  (c) 46 ?
  (d) 37 ?

TEST I will be on Tuesday, Mar. 12 (changed from Mar. 5).

Homework Set VII (2/24)

Do for discussion Wed. 3/6:
      Sect. 2.4, ## 9 (Fig. 2.3.7), 12 (see correction), 21.
      Sect. 3.1, ## 13, 14.
      Sect. 3.2, ## 4, 6.
      ## G3(a), G4, G9(b), G10(b,c).

Hand in Fri. 3/8:
      Sect. 2.4, # 22.
      Sect. 3.1, ## 15, 16.
      Sect. 3.2, ## 5.
      ## G1(b, c), G2(b, c), G3(b), G5, G8, G9(c), G10(d).

Problem Set G

G1. Decompose into the fewest possible trails:
  (a) Fig. 1.2.3 (left).
  (b) Fig. 2.1.9.
  (c) Fig. 2.2.6 (right).

G2. Decompose into the fewest possible paths: (a, b, c) from #G1.

G3. Decide whether the graph is Hamiltonian (i.e., has a Hamilton cycle):
  (a) Fig. 2.1.3.
  (b) Fig. 2.4.1, the Petersen graph.

G4. Verify that, in the proof of Theorem 2.3.2, the first two 1-factors unite to form a Hamilton cycle. Your proof should be valid for all n ≥ 2.

G5. Let G = K_p − edge. Find the edge chromatic number χ'(G) when p is odd, i.e., p = 2n−1 (with n ≥ 2).

G6. (a) Find a graph E which has an Eulerian circuit but no Hamilton cycle.
    (b) Find a graph H which has a Hamilton cycle but no Eulerian circuit.

G7. Produce a decomposition of Fig. 3.2.8 into two 2-factors, using the method of proof of Theorem 3.1.4.

G8. Prove that K_p can be decomposed into p − 1 paths P₁, P₂, ..., P_p−1 for all values of p, not only the even values to which Theorem 2.3.4 applies.

G9. Use the proof method of Theorem 3.2.4 to decompose into subgraphs isomorphic to P₃ :

1. the Petersen graph, Fig. 1.1.13,
2. the icosahedral dodecahedral graph I   D in Fig. 1.2.5 [Egg on face: I is not cubic!],
3. Fig. 2.3.4.

G10. Use the proof method of Theorem 3.1.7 (Listing's Theorem) to decompose into the smallest possible number of trails:

1. the Petersen graph, Fig. 1.1.13,
2. Fig. 2.3.6,
3. Fig. 2.3.7,
4. the Grötzsch graph, Fig. 2.1.6.

G11. (Optional: research problem.) We know some cubic graphs can be decomposed into P₃ subgraphs (e.g., Figs. 2.4.1-2), and some cannot (e.g., Fig. 2.2.6). The counterexample (Fig. 2.2.6) has a bridge, in fact it has three. Must every counterexample have a bridge? That is, can we say that every cubic graph which is connected and has no bridges can be decomposed into P₃ subgraphs?

Homework Set VIIa (3/6)

TEST I will be on Tuesday, Mar. 12. It will cover everything we've done so far (HW Sets I–VII).

Homework Set VIII (3/13, 16)

For Mon. 3/18: Read the handout on line graphs. (This is not in the book. See the definition.)

Do for discussion Tues. 3/19:
      LG, ## 2, 3, 4.
      Sect. 4.1, ## 1, 2, 4, 6.
      Sect. 4.2, ## 2(a), 3.
      # H1(a).

Do for discussion Wed. 3/20:
      LG, # 9.
      Sect. 4.1, ## 7, 8.
      Sect. 4.2, ## 2(b), 4, 6.
      # H2(a).

Hand in Fri. 3/22:
      LG, ## 7, 10.
      Sect. 4.1, ## 3, 5.
      Sect. 4.2, ## 1, 2(c).
      # H1(b).

Problem Set H

H1. This question concerns the proof of Theorem 4.1.2* (that is, the base case k = 2 of Turan's Theorem). You are given the "starting" graph G of the proof, which has no triangle.
  (i) Construct the new graph H in the proof of Theorem 4.1.2*. What are your x and W?
  (ii) Compare the degrees of the vertices in G and H.
  (iii) Compare q_G and q_H. Which is larger? Why is that significant for the proof of the theorem?
  (iv) Compare H to the largest possible triangle-free graph on the same number of vertices. How are they similar?

      (a) For G = G_a, the Petersen graph with one vertex deleted. (See below.)
      (b) For G = G₇, shown below.

H2. The uniqueness of the maximum graph in Theorems 4.1.2* and 4.1.2 is not proved in the book.
  (a) Prove uniqueness in Theorem 4.1.2*.
  (b) Prove uniqueness in Theorem 4.1.2.

Homework Set IX (3/17, 19)

For Fri. 3/22: Read Sects. 5.2-3 and the handout on the Matrix-Tree Theorem.
Problems from the Line Graphs handout are in the Version of March 18; that version gives the date in the heading.

(Notice "for your own good".) The lectures on Fri. 3/22 and Tues. 4/2 are important. If you can teach yourself the material from the readings, you don't need to be there. Otherwise, be there.

Do for discussion Wed. 4/3:
      Sect. 5.2, ## 1, 2, 3, 4(a), 5.
      Sect. 5.3, ## 1, 4, 11(a).
      MT, ## 1, 2.
      LG, # 14 (in Version of 3/18).

Do for discussion Fri. 4/5:
      Sect. 5.2, ## 8, 10.
      Sect. 5.3, ## 3, 7(a), 10(left), 11(b,c).
      MT, # 3.

Hand in Mon. 4/8:
      Sect. 5.2, ## 4(b), 7, 9, 11.
      Sect. 5.3, ## 2, 11(d).
      MT, # 4.
      LG, # 15 (in Version of 3/18).

Homework Set X (3/25, 28)

Homework Set XI (4/10)

Read Sects. 8.1-3. (This is a lot to discuss. Study carefully and come in Tuesday with many questions.)
Added: See Theorem 8.1.A on the relationship between maximal planar graphs and plane triangulations.

Do for discussion Tues. 4/16:
      Sect. 8.1, ## 1-5, 7, 10.
      Sect. 8.2, ## 3, 4.

Do for discussion Wed. 4/17:
      Sect. 8.1, ## 8, 9, 12, 13.
      Sect. 8.2, ## 1, 2.
      Sect. 8.3, ## 2, 3.

Hand in Fri. 4/19:
      Sect. 8.1, ## 6, 11.
      Sect. 8.2, ## 5, 6.
      Sect. 8.3, ## 4, 7.

Definition for Exercise 8.3.7

• A plane triangulation is a plane graph in which every region is a triangle.

TEST II will be on Tuesday, April 23. Monday before the test will be a review day.

Homework Set XII (4/24)

• See the announcements page for explanation of "Kuratowski's Theorem".
• In Sect. 9.1, p. 180: A simple drawing must also satisfy:
      d) no edge passes through any vertex;
      e) whenever edges intersect, they cross.
• We define the girth of a forest (such as a tree) to be infinity. Then the girth of a graph is always ≥ 3.
      See Theorem G, Theorem CR, and Theorem SPL, on the announcements page.

Problem Set I

I1. Show that the graph of Fig. 9.1.16 is nonplanar.

I2. Planar or nonplanar? Prove it!
  (a) Fig. 9.1.19.
  (b) Fig. 9.1.18.
  (c) Fig. 9.1.17.
  (d) Fig. 9.2.1, left.
  (e) Fig. 9.2.1, right.

I3. Prove that cr(P) ≥ 2, where P is the Petersen graph. without using Theorem CR.

I4. (a) Prove that, if p ≥ 11, then K_p has no decomposition into two planar graphs.
  (b) Can K₈ be decomposed into two planar graphs?
  (c) Prove: if p ≥ 17, then K_p cannot be decomposed into three planar graphs.

I5. Do both (i) and (ii) for
  (a) Fig. 2.3.6.
  (b) Fig. 4.2.4.
  (c) Fig. 1.3.3.

      (i) Is the graph planar?
      (ii) Find the crossing number. If you can't calculate it exactly, find out as much as you can about it. For instance, is it = 0 or > 0? Is it = 1? = 2? ≥ 2? ≥ 3? Can you find any upper bound?

I6. Write a complete proof of the 6-Color Theorem.

I7. (a) Prove Theorem G.
  (b) What does it say if g = 3?
  (c) What does it say if G is bipartite?

I8. Use Theorem G to do (a, b, d).
  (a) Prove: A cubic graph with girth g = 6 cannot be planar.
  (b) Prove: A cubic graph with g ≥ 6 cannot be planar.
  (c) Can a cubic graph with g = 5 be planar?
  (d) Find a lower bound on cr(G) when G is cubic and has girth 6.

I9. (a) Prove Theorem CR.
  (b) What does it say if g = 3?
  (c) What does it say if G is bipartite?

I10. Use Theorem CR to solve:
  (a) Find cr(P), P = Petersen graph.
  (b) Find cr(H), H = Heawood graph (Fig. 4.2.4).

Homework Set XIII (5/1)

Read: Sects. 9.3 and 10.3. (In 10.3, omit anything about "schemes", "maximal rotations", and "current graphs", and pp. 235-237.)
Be sure to study the Supplement to Section 10.3 on the announcements page.

Do for discussion Tues. 5/7:
      Sect. 10.3, ## 1, 8, 9.
      ## J2, J3, J5, J7, J8, J9.

Hand in Wed. 5/8:
      Sect. 10.3, ## 7, 10.
      # I9 (added).
      ## J1 cancelled, J4, J6.

Definition

• Embedding a graph in a surface means drawing it on the surface without crossings.

Problem Set J

J1. Prove that cr(K₆ − edge) = 2.

J2. Find θ(P), where P is the Petersen graph.

J3. Prove that θ(K_n) ≥ ceiling[(n+2)/6] for all n ≥ 1.

J4. Let c(G) = the number of cycles in the graph G.
  (a) Prove Theorem M: If c(G) < min(c(K₅), c(K_3,3)), then G is planar. (Hint: Use Kuratowski's theorem.)
  (b) Evaluate the minimum in Theorem M.
  (c) Use (b) to solve Exercise 8.1.3. (If you didn't solve (b), just prove the minimum in (b) is > 3; that should be enough for Exercise 8.1.3.)

J5. Let H = Heawood graph, Fig. 4.2.4.
  (a) Prove σ(H) ≥ 2.
  (b) We know σ(H) ≤ 3. Decide whether σ(H) = 2 or 3.

J6. Find an easy proof that σ(P) ≥ 2, where P = Petersen graph. (Thus σ(P) = 2, by Exercise 9.3.4.)

J7. Try to embed non-planar complete graphs in the torus. Start with K₅ (naturally), and if you succeed, try K₆ and then K₇ and then ....

J8. The same as # J7, for the double torus.
Use theorems in Section 10.3 to decide where to stop embedding in the double torus.

J9. Try to embed non-planar complete bipartite graphs in the torus. Start with K_3,3 (naturally), and if you succeed, try K_3,4 and then K_3,5 and K_4,4 – and then (we're getting into summer plans here) ....
Use theorems in Section 10.3 to decide where to stop embedding in the torus.

Homework Set XIV (5/1)

K4. Compare the lower bound p(g) on the order of a g-cage (see Theorem 4.2.A) to the actual order of every known g-cage given in the book. Which cages have order equal to p(g)? Which have order greater than p(g)? What does it mean when a g-cage has order > p(g)?