Homework Set IX (3/30)

For Fri. 4/1: Read the handouts on graph automorphisms (Aut) and line graphs (LG).

For Mon. 4/4: Read Sects. 4.1 and 4.2.

Do for discussion Tues. 4/5:
## LG.2, LG.3, LG.4; ## Aut.1, Aut.2.
Sect. 4.1, ## 1, 2, 4, 6.
Sect. 4.2, ## 2(a), 3.
# I1(a).

Do for discussion Wed. 4/6:
# LG.9; # Aut.4.
Sect. 4.1, ## 7, 8.
Sect. 4.2, ## 2(b), 4, 6.
# I2(a).

Hand in Fri. 4/8:
## LG.7, LG.10; # Aut.5.
Sect. 4.1, ## 3, 5.
Sect. 4.2, ## 1, 2(c).
## I1(b), I2(b) (# I2(b) is postponed to HW X).

Explanation of grading:

• LG.7: 4 pts., including proof of correctness.
• LG.10: 4 pts.; a clear, complete, and correct description of the line graph is necessary.
• Aut.5: (a) 4 for answer, 4 for proof. (b) 4 for answer. Both need a clear, complete, and correct description.
• 4.1.3, 4.1.5, 4.2.2(c): 4 for correct example, 4 for complete proof.
• 4.2.1, I1(b): Not graded.

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.