Math 381 Homework
Spring 2021

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 class time on Wednesdays (and possibly Thursdays) for class discussion of 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.

Boldface problems were graded. Other problems were not graded.

Due Wed., 2/17:
Read Section 1.1.
Also, read the course information page and the homework instructions.

Do for discussion on Wed. and Thurs., 2/17-18 (not to hand in):
      ## A1–A5 for G = G₁ and G₂.

Hand in Sat. 2/20, 3:00 p.m.:
      ## A1–A5 for G₃, 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.

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?

Homework Set II (2/17)

Due Fri., 2/19: Read Section 1.3 and the automorphisms handout.
Remember to check the announcements page for corrections to the textbook.

Due for discussion Wed., 2/24:
      ## B1(c), B2(c) (think about them for a few minutes; we'll discuss them in class).
      Sect. 1.1, ## 1, 2, 4(a-c), 6.
      Sect. 1.2, # 1, 4, 7.

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

Hand in Sat., 2/27 Sun., 2/28, 3:00 p.m. (by email in PDF format):
      ## B1(a,b), B2(a,b).
      Sect. 1.1, ## 3, 4(d), 5, 7, 8.
      Sect. 1.2, # 5.
      ## C1, C3.

Problem Set B

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

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

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.

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 III (2/24)

For Fri. 2/26: Read the extra theorems for Section 1.3. I also posted some basic graph-theory counting formulas.

Starting with HW III, I will give 4 bonus points for Latex homework.

For Mon. 3/1: Read Section 2.1.

Do for discussion Wed. 3/3:
      Sect. 2.1, ## 1-4, 8, 13, 18, and 9-10 (for P₅, K_4,4, D, and O).
      ## D1, D4.

Do for discussion Thurs. 3/4:
      Sect. 2.1, ## 6, 11, 14, 16, 17.
      # D5.

Hand in Sun. 3/7 by 3:00 p.m.:
      Sect. 2.1, ## 5, 7, 15(a), 19, 20 (see announcement), and 9-10 (for I).
      ## D2, D3, D6, D7(ab),(c),(d).

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.

• 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! There are several others for this section.

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. Here are some theorems that characterize two important kinds of graph. See what you can do. (a) may be a mistake (I don't know myself). (b) is true.

1. 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.
2. Prove Theorem 1.3.C: A graph is a cycle if and only if it is connected and 2-regular.

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

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

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

D7. Find all critical graphs with chromatic number

1. 1.
2. 2.
3. 3.
4. For 4 or higher this is an impossible problem.

Homework Set IV (3/9)

For Thurs. 3/11: Read Sections 2.2, 2.3 and the line graphs handout.

Do for discussion Thurs. 3/11:
      Sect. 2.2, ## 3, 5, 6.
      Sect. 2.3, ## 1-3.
      ## E1(a), E5(a), E7(a,b).

Do for discussion Fri. 3/12:
      Sect. 2.2, ## 8, 9.
      Sect. 2.3, ## 4, 5-7 (for Q₃ and I), 8, 10, 12.
      ## E5(b,c), E7(c), E8-9(a-c).

Hand in Mon. 3/15 Tues. 3/16 (any time, even after midnight):
      Sect. 2.2, ## 4, 7, 10.
      Sect. 2.3, ## 5-7 (for D), 17.
      ## E1(b), E2, E5(d), E6, E7(d), E8(d), E9(c).

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

Grading note

• 2.2.10: I gave 2/4 for only showing the two graphs. I gave 4/4 for also explaining why p=q=4 is the only possibility.

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). How does it compare to the maximum degree Δ(G)?

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.

E8. Find the line graph of each graph.
  (a) P_n for n ≥ 1.
  (b) C_n for n ≥ 3.
  (c) K₄.
  (d) K₄ − edge.

E9. Is the line graph regular? If so, what is the degree (i.e, the degree of each vertex)?
  (a) P_n for n ≥ 1.
  (b) C_n for n ≥ 3.
  (c) K_n for n ≥ 4.

Homework Set V (3/13)

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

Do for discussion Thurs. 3/18:
      Sect. 2.3, # 18(a).
      Sect. 2.4, ## 1, 4, 10.
      Sect. 3.1, ## 1-3, 4 (for Q₃, K_4,4 only), 7 (quiz).
      ## F3(a), F4(a), F8(a), F9.

Do for discussion Fri. 3/19:
      Sect. 2.3, ## 18(b).
      Sect. 2.4, ## 2, 8, 12 (see correction).
      Sect. 3.1, ## 5, 8, 11, 13.
      ## F1(a,b), F5(a), F6, F7(a), F8(b) (quiz).

Hand in Tues. 3/23 | Thurs. 3/25 Fri. 3/26 (any time of day or night):
      Sect. 2.3, # 18(c).
      Sect. 2.4, # 7, 22, 25.
      Sect. 3.1, ## 6, 12, 14.
      ## F1(d), F2, F3(b,c), F4(b,c), F5(b), F8(d), F10.

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

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

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 K_p as mentioned at the bottom of page 39:

1. Consider the family of "star graphs", K_1,i. They are trees; each has i edges. Decompose K_p into subgraphs isomorphic to the star graphs K_1,1, K_1,2, ..., K_1,p−1.
2. (Optional: bonus problem.) Choose a family of trees T_i for i = 1, 2, ..., where T_i has i edges. See if you can decompose K_2n 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 VI (3/22, 25)

For Mon. 3/29: Read the handout "LG" on line graphs. (This is not in the book. See the definition.) For the complement of a graph see the definition.

Do for discussion Wed. 3/31:
      LG, ## 2, 3.
      Sect. 1.3, ## 1, 2, 6.
      Sect. 3.2, ## 1-3.
      Sect. 3.3, ## 1, 4, 5.
      Sect. 4.1, ## 1, 2.
      Sect. 4.2, ## 2(a).
      # H1(a).

Do for discussion Thurs. 4/1 (ha ha! Didn't fool you!):
      LG, # 9.
      Sect. 1.3, ## 11, 14.
      Sect. 3.2, # 4.
      Sect. 3.3, # 17 (see correction).
      Sect. 4.1, ## 4, 6, 7.
      Sect. 4.2, ## 2(b).
      # H2(a).

Hand in Mon. 4/5 (any time) (not due Easter Sunday):
      LG, ## 7, 10.
      Sect. 1.3, ## 7, 10.
      Sect. 3.1, ## 15, 16.
      Sect. 3.2, # 8.
      Sect. 4.1, ## 3, 5.
      Sect. 4.2, # 2(c), 3, 6.
      # 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 VII (3/31)

Midterm exam: April 12–13.

For Thurs. 4/15: Read Sect. 5.3 and the handout on the Matrix-Tree Theorem.
For Fri. 4/16: Read Sect. 6.1.

Do for discussion Fri. 4/16:
      Sect. 5.3, ## 3, 4,7(a), 11(a).

Hand in Mon. 4/19:
      Sect. 5.3, ## 1, 2.

Homework Set IX (4/14, 16, 19)

Read for Mon. 4/19: Sects. 6.2, 7.1. Check the announcements page for the incidence matrix.

Do for discussion Wed. 4/21:
      Sect. 6.1, ## 1-3, 5.
      Sect. 6.2, ## 1, 5.
      Sect. 7.1, ## 1(a), 2(left), 5.

Do for discussion Thurs. 4/22:
      Sect. 6.1, ## 6, 8, 10, 19.
      Sect. 6.2, ## 6, 9.
      Sect. 7.1, ## 3, 6.

Hand in Mon. 4/26 (not Fri. 4/23) by 6:00 p.m. any time:
      Sect. 6.1, ## 7, 11, 21(a,b,c).
      Sect. 6.2, ## 7, 10, 12, 14.
      Sect. 7.1, ## 2(right).
      ## I1, I2 (optional), I3 (optional).

Voluntary bonus Challenge Problems, due any time before the final exam:
      # I4, any parts.

Problem Set I

I1. Suppose G is a connected digraph with p vertices. Prove that the rank of the incidence matrix M(G) equals p − 1. (See the announcements page for hints.)

I2. Suppose G is a strongly conservative digraph. Then there is an edge labelling f using the numbers 1, 2, ..., q, once each, such that f satisfies Kirchhoff's Current Law (KCL) and also for every integer h, the labelling f+h satisfies KCL. Remember that f+h is the labelling that assigns edge e the label f(e)+h.

I3. Suppose G is a strongly conservative digraph. Then for every vertex v, the number of edges with head at v = the number of edges with tail at v. (Hint: Use #I2.)

I4. The proof that K_3,3 is nonconservative that we worked out in class on 4/21, based on Alex's suggestion, suggested possible generalizations that could use the same idea.

1. Proposed Theorem 1. If G is a bipartite cubic graph of order p where p ≡ 4, 6 (mod 8), then G is nonconservative. (This includes K_3,3 as the simplest case. It also includes the Heawood graph; see the Cages section.)
2. Proposed Theorem 2. If G is any bipartite graph with q edges where q ≡ 1, 2 (mod 4), then G is nonconservative. (This is a generalization of Proposed Theorem 1.)
3. Is there a theorem involving p, for bipartite graphs that are k-regular for arbitrary k (the case k = 3 should be Proposed Theorem 1).
4. Is there a similar theorem that is not limited to bipartite graphs? It would need a new idea.

Homework Set X (4/14, 26)

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

Do for discussion Wed. 4/28:
      Sect. 8.1, ## 1-5, 7, 10.
      ## J4(a).

Do for discussion Thurs. 4/29:
      Sect. 8.1, ## 8, 9, 12, 13.
      Sect. 8.2, ## 1, 2.
      ## J1(a,b).

Do for discussion Fri. 4/30:
      Sect. 8.2, ## 3, 4.
      Sect. 8.3, ## 2, 3.

Hand in Fri. 4/30 Mon. 5/3 before class:
      Sect. 8.1, # 11.
      Sect. 8.2, ## 5, 6.
      Sect. 8.3, ## 4, 7.
      ## J1(c), J2, J3, J4(b-c).

Corrections and Additions

• Definition for Exercise 8.3.7: A plane triangulation is a plane graph in which every region is a triangle.
• 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 on the announcements page.

Problem Set J

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

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

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

J4. Use Theorem G to do (a, b).
  (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?

Homework Set XI (5/3)

• 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 CR and Theorem SPL on the announcements page.

Problem Set K

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

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

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

K4. Use Theorem CR to solve:
  (a) Find cr(P), P = Petersen graph. Is it easier than #K3?
  (b) Find cr(H), H = Heawood graph (Fig. 4.2.4).

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

K6. Write a complete proof of the 4-Color Theorem for Triangle-Free Graphs.

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

K8. Use Theorem G to find a lower bound on cr(G) when G is cubic and has girth 6.

Homework Set XII (5/11)

Read: Sects. 9.3 (for Wed. 5/12; you already saw most of this in class) and 10.3 (for Thurs. 5/13). (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 Thurs. 5/13 and Fri. 5/14:
      Sect. 9.3, ## 3, 13.
      Sect. 10.3, ## 1, 8, 9.
      ## L2, L3, L5, L7, L8.

Hand in Sun. 5/16:
      Sect. 9.3, ## 1, 4.
      Sect. 10.3, ## 7, 10.
      ## L4, L6, L9.

Definition

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

Problem Set L

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

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

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

L4. 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. If you can't find the exact minimum, just prove it is > 3.
  (c) Use (b) to solve Exercise 8.1.3.

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

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

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

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

L9. 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 XIII (5/11)

M4. Prove Theorem 4.2.A.

M5. Compare the lower bound p(g) on the order of a g-cage (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)?

M6. I'll define a graph R. V(R) is the set of all unordered pairs ij of elements of the set S₅ = {1, 2, 3, 4, 5}. (I use the simplified notation ij to mean the set {i, j}.) The pair {ij, kl} is an edge when i, j, k, l are four distinct elements of S₅.
  (a) Prove that R is isomorphic to the Petersen graph, P.
(In fact, this is one way to define the Petersen graph. From now on I will call this graph P, as there is no difference.)
  (b) Prove that P is the complement of the line graph of K₅.
  (c) Prove that for every two edges in P, say e and e', there is an automorphism f of P such that f(e) = e'.
(This fact is useful in problems like #K3, because all edges can be treated at once instead of in three cases.)