Math 381 Homework


Go to announcements | course information.

Index of Homework Assignments and Problem Sets
(on separate pages)



General Advice
on homework problems

Besides finding the answer, always try to explain, as well as you can, how you know you have the correct answer.

When solving problems, a systematic solution is better than guesswork. You often may find a solution by intelligent guessing, but then you should look for a way of showing that your solution is correct. This part needs to be systematic if it is to be completely convincing. (This will be clearer after a few days of class!)

Allow 15 minutes per problem (minimum) before you give up, even if you feel you're getting nowhere. These problems need time for thought. If you're still stuck, go on to another problem. Return to the sticky problem later (say, the next day). Often, it then looks easier because you tried hard the first time and then gave your mind time to grind it up--I mean, to come up with ideas. To get the advantage of this method, you have to start the problems well ahead of time. Last-minute effort will not work well in this class.

Rules for hand-in homework.

(1) Hand in a final draft: neat work that is well organized and not cramped. Use as much space as you need. Please also leave some extra space between problems for our comments.

(2) You may discuss hand-in HW with other people, but you must write it up in your own words.

(3) No little stubbies from tearing a page out of your notebook. Remove them neatly.

(4) Fasten the pages securely. That means stapling or a paper clip, not folding the paper over and/or tearing it (not secure!).

I reserve the right to reduce grades for not following these rules.



Graph Theory Homework: Complete



Homework Set I (1/21)

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 = G1 (do this first) and G2, G4.
Also, read to page 8 in the textbook.

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

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


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 = G1, G2, G3. (Omit G4.)

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?

The four graphs.



Homework Set Ia (1/28)

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.



Homework Set II (1/23)

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

Definitions will be found on the announcements page.

The graph G<sub>0</sub>.

B1. This concerns Theorem 1.1.2 and the example G0. I'll follow the book's notation. NOTE: There are some errors in this question. The corrected version is Problem # BB1 in HW Set IIa (see below). The sequence
   (S1) (4, 4, 4, 3, 3, 3, 2, 2, 1)
is known to be graphic, because it is the degree sequence of G0. From (S1) the rule of Theorem 1.1.2 gives
   (S2) (3,3,2,2,3,2,2,1).

  1. (a) In this example what are s, t1, ..., ts, n, d1, ..., dn ? (Give their values.)
  2. (b) Label the vertices of G0 by S, T1, ..., Ts, D1, ..., Dn as in the proof of the theorem. (Note: Do not choose S = h.)
  3. (c) If you delete vertex S, does the new graph G0 - S have (S2) as its degree sequence?
  4. (d) Use the method in the proof to modify G0 so that, when you delete S, you do get (S2) as the degree sequence of the new graph.

B2. In which graphs is the whole vertex set V the only separating set?

B3. In G2 from Homework I, find the values of (a) kappa(1, 5), (b) kappa(2, 6). Use Menger's Vertex Theorem to prove you are correct: i.e., find the internally disjoint paths that the theorem tells us exist.

B4. The same as B3, but for kappa(v3, v5) in G3 from Homework I.



Homework Set IIa (1/30)

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


Problem Set BB

The graph G<sub>0</sub>.

BB1. This concerns Theorem 1.1.2 and the example G0. 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 G0. 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, t1, ..., ts, n, d1, ..., dn ? (Give their values.)
  2. (b) Label the vertices of G0 by S, T1, ..., Ts, D1, ..., Dn 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 G0 - S have (S3) as its degree sequence?
  4. (d) Use the method in the proof to modify G0 so that, when you delete S, you do get (S3) as the degree sequence of the new graph.



Homework Set III (1/23)

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.

The graph G<sub>0</sub>.

C4. Show that the graph G0 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 G0.

C5. In G2 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(v3, v5) in G3 from Homework I.



Homework Set IV (2/6-9)

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 P5, K4,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


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.



Homework Set V (2/20)

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 Q3 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


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(K2n) = {0, 1, 2, ..., 2n-2, x}. We have a standard way to decompose K2n into 1-factors (see Section 2.2). In K8, 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.



Homework Set VI (2/27)

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(K2n+1) = {0, 1, 2, ..., 2n-1, x}. We have a standard way of decomposing K2n+1 into Hamilton cycles (see Section 2.3). In K11, which "standard" Hamilton cycle contains the edge
(a) 23 ?
(b) 3x ?
(c) 46 ?
(d) 37 ?

F3. Prove that Kp can be decomposed into p - 1 paths P1, P2, ..., Pp-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.



Homework Set VII (2/27)

Read Section 3.1.

Do for discussion Wed. March 10:
Sect. 3.1, ## 1-3, 4 (for I, D, K4,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).

See the corrections for Section 3.1.


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) as in #G1.

G3. Decide whether the graph is Hamiltonian:
(a) Fig. 2.1.3.
(b) Fig. 2.1.6.



Homework Set VIII (3/10)

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 Kp can be decomposed into p - 1 paths P1, P2, ..., Pp-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.



Homework Set VIIIa and Problem Set HH (3/17)

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

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



Homework Set IX and Problem Set I (3/26)

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 qG and qH. 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 = Ga, the Petersen graph with one vertex deleted. (See below.)
(b) For G = G7, 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.

Graphs G<sub>a</sub> and G<sub>7</sub>.



Homework Set X (4/1)

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



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 K3,3 is the unique 4-cage.



Homework Set XI and Problem Set K (4/14)

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



Problem Set K

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

K2. (a) Prove that, if p >= 11, then Kp has no decomposition into two planar graphs.
(b) Can K8 be decomposed into two planar graphs?
(c) Prove: if p >= 17, then Kp 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.)



Homework Set XII and Problem Set L (4/23)

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(K6 - edge) >= 2.



Homework Set XIII and Problem Set M (4/30)

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



Problem Set M

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

M2. Prove that theta(Kn) >= 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(K5), c(K3,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.)



Extra Problems (4/30)

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.


Go to
announcements | course information | homework list | previous homework

Problem Set N

N1. Let N5 = {1,2,3,4,5}. Define a graph G5 by V(G5) = the set of all unordered pairs ij of elements of N5, with two pairs ij and kl adjacent if their intersection is empty.
(a) Prove that G5 cong P, where P = Petersen graph.
(b) Prove that, for any two vertices x, y of P, there is an isomorphism phi of P with itself such that phi(x) = y. (Technically, phi is the one-to-one correspondence between vertex sets. You can think of it as the function which tells you which vertex y will be relabelled x in the relabelling process.)

N2. The graph G2 is shown. Find out as much as you can about its crossing number.

N3. (a) Find a largest graph with 11 vertices and all degrees divisible by 3. (b) Even better, find all (nonisomorphic) largest such graphs.

N4. In class we proved that theta(G) <= cr(G)+1. Can you improve on this, e.g., by reducing the upper bound?



Go to announcements | course information.