Math 381 Homework
Spring 2025


Go to homework advice | announcements | course information | syllabus.

The homework advice page has advice about how graph theory problems should be done, not entirely the same as problems in other 300-level math courses.

We use some class time for discussing graph theory, including homework problems and questions about the text or anything else.

Important homework rule: In solving homework problems, you are not allowed to justify your answer by appeal to anything you find outside our book, or to anything in the book that's ahead of the readings we've done.


Index of Homework Assignments

Latex instructions in LaTeX, PDF.

Boldface problems were graded. Other problems were not graded.
§ means "section".
(corr) means correction (with a link to the correction on the announcements page).


Homework Set I (assigned 1/22-24)

Read Section 1.1 for Fri., 1/24.
Also, read the
course information page and the homework instructions.

Hand in Mon. 1/27:
      § 1.1, # 4.


Homework Set II (assigned 1/24-27)

Read Section 1.2 for Mon.-Wed., 1/27-29.

Do for discussion on Wed. 1/29 (not to hand in):
      § 1.1, # 2a;   § 1.2, ## 2, 7.

Hand in Fri. 1/31:
      § 1.1, ## 1, 2b, 5, 7 (see
correction).
      § 1.2, ## 1, 3, 5, 6, 9.


Homework Set III (assigned 2/2)

For the class discussion, come up with ANY IDEAS and bring them along!

Four graphs.

Due Wed., 2/5:
Read Section 1.3 for Mon., 2/3.

Do for discussion on Wed., 2/5 (not to hand in):
      ## A1–A5 for G = G1 and G2.

Hand in 2/5:
      ## A1–A5 for G3, G4. Grading note: I didn't expect proofs in this HW set.


Problem Set A

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

I'll write G for G1, G2, G3, G4.

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.

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?

A5. Is the graph planar, i.e., can you draw it in the plane without crossings?


Go to homework index.

Homework Set IV (2/7)

Due Mon., 2/10: Read Section 2.1 and the automorphisms handout.
Always remember to check the announcements page for corrections to the textbook.

Do for discussion Mon. 2/10:
      1.3, ## 4, 5, 7.
      2.1, # 3.

Hand in Mon., 2/10:
      1.3, ## 6, 12, 13, 20.
      2.1, ## 1, 2.
      ## B1, B2.


Problem Set B

B1. Find a pair of graphs, G and H, that are not isomorphic but which have the same degree sequence and are both connected.

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

B3. 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. Remember that a walk is not necessarily a path.


Homework Set V (2/14)

For Mon. 2/17: Read the chromatic polynomial handout.
Starting now, I will give 4 bonus points for LaTeX homework.

Do for discussion Mon. 2/17: ## C1, C4.

Hand in Fri., 2/21:
      ## C2, C3, C5.
      2.1, ## 3, 4 (corr), 6, 7.
Grading note on 2.1.4: I graded one graph. 4/4 for proving chromatic number, 4/4 for a critical subgraph with the same chromatic number.
Grading note on C5: Each part was graded separately.


Problem Set C

C1. Let Gn be Kn with one edge deleted. Find the chromatic polynomial of Gn, χGn(k).

C2. Find the chromatic polynomial of a tree of order n. (Recommendation: Start with n = 1, 2, 3. Use induction.)

C3. Find the chromatic polynomial of C4.

C4. How is the chromatic number χ(G) of a graph G related to the chromatic polynomial χG(k)?

C5. Apply the proof method of Theorem 2.1.6 (not the statement of the theorem) to decide whether the following graphs are or are not bipartite.

  1. Figure 1.1.13.
  2. Figure 1.2.7 middle.
  3. Figure 2.1.4.


Go to homework index.

Homework Set VI (2/23)

For Mon. 2/24: Read Section 2.2 and the line graphs handout.
Note: Theorem 2.2.4 is invalid for n = 1.

Do for discussion Wed. 2/26:
      2.1, ## 11, 13, 16, 17. Also 9-10 for K4,4 and O.
      2.2, # 5.
      ## D1, D4.

Hand in Fri., 2/28:
      1.3, ## 10, 21.
      2.1, ## 5, 8, 15(a), 19, 20 (see announcement).
      2.2, ## 3, 6.
      ## D2, D3, D5.

In general (see homework advice), you should start on our homework well ahead of the due date, because some of the problems are easy but some take a lot of thought, which is best done in pieces, even on successive days. That's particularly true in this set.


Problem Set D

D1. Suppose G is a connected graph whose average degree is > 2. (Hint: See page 19.) Prove that it is possible for G to have exactly 2 cycles.

D2. Suppose G is a connected graph whose average degree is 3. (Hint: Use a similar idea to D1, but you have to add something.)
  (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. Prove or disprove Alleged Theorem 1.3.B: A graph G is a tree if and only if it is connected and its average degree is < 2.

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.


Go to homework index.

Homework Set VII (3/2)

For Mon. 3/3: Read Sections 2.3 and 2.4.
Regarding p. 45 on components, see the
correction.
The last line on p. 38, the one for (Cn), 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.)

Do for discussion M 3/3:
      2.3, ## 4, 5-7 (for Q3), 18(a).
      2.4, # 10.
      ## E1(a), E2(a,d).

Do for discussion W 3/5:
      2.2, # 9.
      2.3, ## 8, 10, 12, 18(b).
      2.4, ## 2, 8.
      ## E4(a,b), E5(a,b), E6(a,b).

Hand in Fri. 3/7:
      2.2, ## 4, 10.
      2.3, ## 1, 2, 5-7 (for D), 17, 18(c).
      2.4, # 4, 22, 25.
      ## E1(b), E2(b,c), E3, E4(c,d), E5(d), E6(c).
Grading note on 2.2.10: I give 4/4 for showing the two graphs and another 4/4 for also explaining why p=q=4 is the only possibility.

Homework Set VIIa (3/2)

For M 3/17: Read Section 3.1, pp. 49-51. Do for discussion:
      2.3, ## 13.
      2.4, ## 7, 12 (corr), 13.
      3.1, ## 1, 3.
      # E8.


Problem Set E

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

E2. Let V(K2n) = {0, 1, 2, ..., 2n−2, x}, as in Section 2.2. 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.

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

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

E5. Find the line graph of each graph.
  (a) Pn for n ≥ 1.
  (b) Cn for n ≥ 3.
  (c) K4.
  (d) K4 − edge.

E6. Is the line graph regular? If so, what is the degree (i.e, the degree of each vertex)?
  (a) Pn for n ≥ 1.
  (b) Cn for n ≥ 3.
  (c) Kn for n ≥ 4.

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

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


MIDTERM EXAM: Fri., March 21, covering Chapters 1-2, also chromatic polynomial and line graphs.


Go to homework index.

Homework Set VIII (3/23)

Read Section 3.1 for Mon., 3/24. See the corrections for Section 3.1.
The proofs in 3.1 show you how to construct trails, decompositions, etc.

Recommendation: To better understand the 4-dimensional cube (or "tesseract"), read the short story "—And He Built a Crooked House".

Do for discussion Wed. 3/26:
      Sect. 3.1, ## 1-3, 4 (for Q3, K4,4 only), 5, 7, 8, 11, 13.
      ## F3(a), F4(a), F7(a), F8(a).

Hand in Mon. 3/31:
      Sect. 2.4, # 12 (see correction).
      Sect. 3.1, ## 6, 12, 14.
      ## F2, F3(b,c), F4(b,c), F8(d), F9, F10.


Problem Set F

F2. We define a graph to be connected if for any two vertices, there is a path between them (page 17). A fundamental fact is that, if there is a walk between vertices u and v, then there is a path between them (see Connection Theorem). Prove this. (It is possible that the proof of B3 may suggest an idea.)

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

F4. Decompose into the fewest possible paths: (a, b, c) from #F3. How do these answers compare to those in F3?

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

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

F7. Regarding tree decompositions of Kp as mentioned at the bottom of page 39:

  1. Consider the family of "star graphs", K1,i. They are trees; each has i edges. Decompose Kp into subgraphs isomorphic to the star graphs K1,1, K1,2, ..., K1,p−1.
  2. (Optional: bonus problem.) Choose a family of trees Ti for i = 1, 2, ..., where Ti has i edges. See if you can decompose K2n into subgraphs isomorphic to these trees, one per tree. (All paths or all stars are done.) This is an open-ended question; there are many possible choices for the family of trees. Can you solve a few?

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

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

F10. (Bonus problem.) Exercise 2.4.14 asks you to decompose the Petersen graph into 3 subgraphs isomorphic to each other, that is, they are all isomorphic to some graph H. The bonus question is: How many nonisomorphic graphs H are there, for which this is possible? Each must have 5 edges, since Petersen has 15 edges. This is an open-ended question; see how many H's you can come up with.


Homework Set IX (3/28)

For Mon. 3/31 read Section 4.1.
For Fri. 4/4, read Section 5.2.

Do for discussion Wed. 4/2 & Fri. 4/4:
      Sect. 4.1, ## 1, 2, 4, 6.
      Sect. 4.2, ## 2(a), 4, 6.
      # G1(a), G2(a).

Hand in Mon. 4/7:
      Sect. 4.1, ## 3, 5, 7.
      Sect. 4.2, ## 2(b), 3, 5(a).
      # G1(b), G2(b).


Problem Set G

G1. This question concerns the proof of Theorem 4.1.2* (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.

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


Go to
homework index | announcements | course information | syllabus.