Math 381 Homework

This assignment is for discussion in class (except as called "Hand In"). Come up with ANY IDEAS at all and bring them along!

Due Thurs., 1/22:
##A1, A2, A4 for G = G₁ (do this first) and G₂, G₄.
Also, read to page 8 in the textbook.

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

Hand in Fri. 1/23:
##A1, A2, A4 for G₃.

Problem Set A

Some terminology about a graph:

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 vertices 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?

Hand in Thurs., 1/29:
## AA1, AA2.
Do at least parts (a); do more if you can in a reasonable amount of time. Don't spend a lot of time on these questions.

Problem Set AA

AA1. This problem concerns ways of testing graphs for being isomorphic or nonisomorphic. In each part, suppose G and H are isomorphic graphs.

1. Show that |E(G)| = |E(H)|.
2. Show that either G and H are both connected, or they are both disconnected.
3. Show that G and H have the same degree sequence.

The point is that, if G and H are graphs that fail any one of these properties, then they cannot be isomorphic (by contradiction). But the converse is not true, as the next problem shows.

AA2. For each property in # 1, find a pair of graphs, G and H, that are not isomorphic but which fail the property. Specifically, do these:

1. Find G and H that have the same number of edges.
2. Find G and H that are both connected and have the same number of edges. Also, find G and H that are both disconnected and have the same number of edges.
3. Find G and H that have the same degree sequence and are both connected.

For Mon. 1/26: Read Sections 1.1, 1.2.

Do for discussion Thurs. 1/29:
Sect. 1.1, ## 1, 2, 4(a-c), 6, 9(a).
Sect. 1.2, # 1, 5, 7, 8.
# B3(a).

Do for discussion Fri. 1/30:
Sect. 1.2, ## 2, 3.
## B1, B2, B3(b).

Hand in Mon. 2/2:
Sect. 1.1, ## 3, 4(d), 5, 7, 8, 9(b).
Sect. 1.2, ## 4, 6.
# B4.

Problem Set B

Do for discussion Thurs. 2/5 (additional problem):
# BB1.

Problem Set BB

BB1. This concerns Theorem 1.1.2 and the example G₀. I'll 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, rearranged in descending order, is
   (S3) (3,3,3,2,2,2,2,1).

1. (a) In this example what are s, t₁, ..., t_s, n, d₁, ..., d_n ? (Give their values.)
2. (b) 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. (c) If you delete vertex S, does the new graph G₀ - S have (S3) as its degree sequence?
4. (d) 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.

For Mon. 2/2: Read Section 1.3.

Do for discussion Thurs. 2/5:
Sect. 1.2, # 9 (graphs 1 and 3 only).
Sect. 1.3, ## 1, 2, 5, 11.
## C2, C5(a).

Do for discussion Fri. 2/6:
Sect. 1.3, ## 12-14, 16.
## C3, C5(b).

Hand in Mon. 2/9:
Sect. 1.2, # 10 and the rest of # 9.
Sect. 1.3, # 7.
## C1, C4, C7.

Problem Set C

C1. CORRECTION: Omit this problem.

C2. In the graph F of Figure 1.1.16:
(a) Find a longest path P. (Call its endpoints x and y.)
(b) Pick an edge e of P which lies in a cycle of F. In F - e, find a path connecting x and y.
(c) 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 why, if G has a path connecting a to b, so does G - e.

C4. Show that the graph G₀ is not a tree by using the proof of the first half of Theorem 1.3.5. Namely, pick any two paths you like between a and e, and use the method in the proof to contruct a cycle in G₀.

C5. In G₂ from Homework I, find the values of
(a) lambda(1, 5), (b) lambda(2, 6).

Use Menger's Edge Theorem to prove you are correct: i.e., find the pairwise edge-disjoint paths that the theorem tells us exist.

C6. The same as C5, but for lambda(v₃, v₅) in G₃ from Homework I.

For Mon. 2/9: Read Section 2.1.

Do for discussion Thurs. 2/12:
Sect. 2.1, ## 1-4, 8, 13, 18, and 9-10 (for P₅, K_4,4, D, and O).
## D1, D3.

Do for discussion Fri. 2/13:
Sect. 2.1, ## 6, 11, 14, 16, 17.
# D4.

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

Corrections

• 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.)

Problem Set D

D1. Suppose the average degree of a graph G 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 chi(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.

For Mon. 2/23: Read Sections 2.2, 2.3.

Do for discussion Thurs. 2/26:
Sect. 2.2, ## 3, 5, 6, 8, 9.
Sect. 2.3, ## 1, 3, 5.
## E1(a), E3(a).

Do for discussion Fri. 2/27:
Sect. 2.3, ## 4, 6-7 (for Q₃ and I), 8, 10, 18(a).
## E2, E3(b-c).

Hand in Mon. 3/1:
Sect. 2.2, ## 4, 7, 10.
Sect. 2.3, ## 2, 5-7 (for D), 18(c).
## E1(b), E3(d).

Corrections

• The graph I in Figure 1.2.5 is the one without a label. (It's the icosahedral graph.)
• Theorem 2.2.4 is valid only for n >= 2.
• 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 actually equivalent to the printed line, but the printed line doesn't follow the pattern it's supposed to.)

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.

E3. 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.

Read Section 2.4.

Do for discussion Thurs. March 4:
Sect. 2.3, ## 12, 17.
Sect. 2.4, ## 1, 3, 5, 8, 10.
## F1(a, b), F2(a).

Do for discussion Fri. March 5:
Sect. 2.3, # 18(b).
Sect. 2.4, ## 4, 12, 21.
## F1(d), F2(b, c), F4.

Hand in Mon. March 8:
Sect. 2.4, ## 7, 9 (Fig. 2.3.7), 22, 25.
## F1(c), F2(d), F3.

Problem Set F

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

F2. 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 ?

F3. 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.

F4. 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.

Read Section 3.1.

Do for discussion Wed. March 10:
Sect. 3.1, ## 1-3, 4 (for I, D, K_4,4 only), 7, 8, 11, 14.
## G1(a), G2(a), G3.

Hand in Mon. March 15:
Sect. 3.1, ## 1 (for O), 5, 6, 12, 13, 15, 16.
## G1(b, c), G2(b, c), G3(b).

Read Sects. 3.2 and 3.3.

Do for discussion Thurs. 3/18:
Sect. 3.2, ## 1-3, 8.
Sect. 3.3, ## 1-4, 6.

Do for discussion Fri. 3/19:
Sect. 3.2, ## 4, 6.
Sect. 3.3, ## 7, 8, 17.
## H1, H2.

Hand in Mon. 3/22:
Sect. 3.2, ## 5.
Sect. 3.3, ## 16, 20.
## H3, H4.

Correction

In Exercise 3.3.17, the graph you find should also be connected, in addition to the other properties that were specified.

Problem Set H

H1. (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.

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

H3. Correction: This is the same as # F3. Please omit. 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.

H4. For ambitious students, prove:
Lemma H4. In a pseudograph G, if there is a trail with endpoints a and b, then there is a path with endpoints a and b.

Do for discussion on Mon. 3/22:
## HH1(a), HH2(a).

Do for discussion on Wed. 3/24:
## HH1 and HH2: in each, do one or two of (b,c,d).
# HH3.

Problem Set HH

HH1. 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 graph I in Fig. 1.2.5,
3. Fig. 2.3.4,
4. the Tutte graph, Fig. 2.3.5.

HH2. 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.

HH3. Do your best to give a correct proof that, in the infinite graph G shown here, each of the three lobes hanging off vertex x has a 1-way Eulerian trail. (All the lobes are the same, but I only drew a large part of one of them.)

For Mon. 3/29:
Read Sects. 4.1 and 4.2.

Do for discussion Thurs. 4/1:
Sect. 4.1, ## 1, 2, 4, 6.
Sect. 4.2, ## 2(a), 3.
# I1(a).

Do for discussion Fri. 4/2:
Sect. 4.1, ## 7, 8.
Sect. 4.2, ## 2(b), 4, 6.
# I2(a).

Hand in Wed. 4/14:
Sect. 4.1, ## 3, 5.
Sect. 4.2, ## 1, 2(c).
## I1(b), I2(b).

Problem Set I

I1. 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.

I2. 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.

Read Sect. 8.1 and Sect. 9.1. The proof of Theorem 9.1.7 is optional. The most interesting thing about the proof of Theorem 9.1.6 is that it uses Turán's Theorem!

Do for discussion Thurs. 4/15:
Sect. 8.1, ## 1-5, 7, 10.
# J1.

Do for discussion Fri. 4/16:
Sect. 8.1, ## 8, 9, 12, 13.
Sect. 9.1, ## 3, 4, 8, 12, 13.
## J3, J4(a, c, d).

Hand in Mon. 4/19:
Sect. 8.1, ## 6, 11.
Sect. 9.1, # 1, 7, 11.
## J2, J4(b, e), J5.

Definitions and Corrections

• In Sect. 9.1, p. 180 and Exercise 9.1.11: Kuratowski's Theorem means the combination of Theorems 9.1.1 and 9.1.2 (although 9.1.1 is relatively easy and is not the part he's famous for).
• In Sect. 9.1, p. 180: A simple drawing must also satisfy
      d) no edge passes through any vertex.

Problem Set J

J1. Let G be the Grötzsch graph (Fig. 2.1.6).
(a) Prove chi(G) = 4.
(b) Is G critical?

J2. Find chi'(Z) where Z is the graph of Fig. 2.3.1.

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

J4. 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.

J5. Prove that K_3,3 is the unique 4-cage.

Read for Mon. 4/19: Sect. 8.3; and also Sect. 8.2, omitting the part about edge 3-coloring (Theorem 8.2.1, Theorems 8.2.3-5, and Theorem 8.2.7). The points to focus on are: coloring a map, mormal maps, Lemma 8.2.2, and the dual graph.

Read for Wed. 4/21: Sect. 8.4.

Do for discussion Thurs. 4/22:
Sect. 8.2, ## 3, 4.
Sect. 8.3, ## 2, 3.
Sect. 8.4, ## 1, 2, 4, 7.
Sect. 9.1, ## 5, 6, 14.
## K1, K3(a).

Do for discussion Fri. 4/23:
Sect. 8.3, ## 4, 7.
Sect. 8.4, ## 5, 9.
## K2(a,b), K3(b), K4.

Hand in Mon. 4/26:
Sect. 9.1, # 15.
Sect. 8.2, ## 5, 6.
Sect. 8.4, ## 3, 6, 11.
## K2(c), K3(c).

Definitions and Corrections

• Exercise 8.2.6: Assume G is connected.
• Definition for Exercise 8.3.7: A plane triangulation is a plane graph in which every region is a triangle.
• Exercise 8.4.9 should read: Find the smallest graph that is planar and regular of degree 3 and has a plane drawing where every edge has the same geometric length.
• Definition: A plane drawing (of a graph) is called stretchable if its edges can be straightened--the vertices can be shifted around if necessary. (I'll discuss this in class.)
• The proof of Theorem 8.4.1 is not stated exactly right in the book. In the middle, what is stretchable is not G - h but the plane drawing of it that we already have. So what we have to prove is not that all planar graphs are stretchable, but that all plane drawings are stretchable.

Problem Set K

K1. Prove that cr(P) >= 2, where P is the Petersen graph.

K2. (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.

K3. 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?

K4. Write a complete proof of the 6-Color Theorem: Every planar graph can be colored in 6 colors. (Hint: Try induction on the number of vertices.)

Do for discussion Mon. 4/26:
Sect. 8.4, # 8.
## L1(a), L2(a).

Do for discussion Wed. 4/28:
## L1(b), L2(b-d), L3.

Problem Set L

Theorem L. If G is a planar graph and has girth g (where 3 <= g < infinity), then q <= [g/(g-2)](p-2).

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

L2. Use Theorem L 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.

L3. Prove Theorem L.

L4. Prove that cr(K₆ - edge) >= 2.

Read Sects. 9.2 and 9.3.

Do for discussion Wed. 5/5:
Sect. 9.2, ## 1-4, 6, 7.
Sect. 9.3, ## 1-4, 6, 8.
## M1, M3, M4(a).

Do for discussion Thurs. 5/6:
Sect. 9.3, # 7.
## M4(b), M5.

Hand in Thurs. 5/6:
Sect. 9.3, ## 5, 9.
# M2.

Definitions, Statements, and Corrections

• Theorems 9.2.1 and 9.2.2 require the assumption that p >= 3.
• The lower bound theta(K_n) >= floor[(n+7)/6] stated on page 192 is lengthy to prove. But the same formula can be rewritten as theta(K_n) >= ceiling[(n+2)/6], whose proof is easy and short. (See Problem K5.)

Problem Set M

M1. Find theta(P), where P is the Petersen graph.

M2. Prove that theta(K_n) >= ceiling[(n+2)/6] for all n >= 1.

M3. 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.)

M4. Let H = Heawood graph, Fig. 4.2.4.
(a) Prove sigma(H) >= 2. (Hint: One way is to use Theorem L in Homework Set XII.)
(b) We know sigma(H) <= 3. Decide whether sigma(H) = 2 or 3.

M5. Prove sigma(P) >= 2, where P = Petersen graph. (Thus sigma(P) = 2, by Exercise 9.3.4.)

These problems are for extra study; they are recommended but not required. They may need more thought than most of the homework problems have. We may discuss them in class during the last days.