Go to announcements | course information.

(on separate pages)

- Homework Set I and Problem Set A (1/21) (On a separate page for easy access.)
- Homework Set Ia and Problem Set AA (1/28) (On a separate page for easy access.)
- Homework Set II and Problem Set B (1/23) (On a separate page for easy access.)
- Homework Set IIa and Problem Set BB (1/30) (On a separate page for easy access.)
- Homework Set III and Problem Set C (1/23)
(On a separate page for easy access.)
**Correction: Omit problem # C1.** - Homework Set IV and Problem Set D (2/6-9) (On a separate page for easy access.)
- Homework Set V and Problem Set E (2/20) (On a separate page for easy access.)
- Homework Set VI and Problem Set F (2/27) (On a separate page for easy access.)
- Homework Set VII and Problem Set G (2/27) (On a separate page for easy access.)
- Homework Set VIII and Problem Set H (3/10) (On a separate page for easy access.)
- Homework Set VIIIa and Problem Set HH (3/17) (On a separate page for easy access.)
- Homework Set IX and Problem Set I (3/26) (On a separate page for easy access.)
- Homework Set X and Problem Set J (4/1) (On a separate page for easy access.)
- Homework Set XI and Problem Set K (4/14) (On a separate page for easy access.)
- Homework Set XII and Problem Set L (4/23) (On a separate page for easy access.)
- Homework Set XIII and Problem Set M (4/30) (On a separate page for easy access.)
- Extra Problems (4/30) (On a separate page for easy access.)

All the assignments are together on this page; each is also on a separate page for easy printing.

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.

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

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_{1} (do this first) and G_{2}, G_{4}.

Also, read to page 8 in the textbook.

Due Fri. 1/23:

#A3 (again, do G_{1} first).

Hand in Fri. 1/23:

##A1, A2, A4 for G_{3}.

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_{1}, G_{2}, G_{3}. (Omit G_{4}.)

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.

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

- Show that |E(G)| = |E(H)|.
- Show that either G and H are both connected, or they are both disconnected.
- 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:

- Find G and H that have the same number of edges.
- 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.
- 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.

Definitions will be found on the announcements page.

B1. This concerns Theorem 1.1.2 and the example G_{0}. 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 G_{0}. From (S1) the rule of Theorem 1.1.2 gives

(S2) (3,3,2,2,3,2,2,1).

- (a) In this example what are s, t
_{1}, ..., t_{s}, n, d_{1}, ..., d_{n}? (Give their values.) - (b) Label the vertices of G
_{0}by S, T_{1}, ..., T_{s}, D_{1}, ..., D_{n}as in the proof of the theorem. (Note: Do*not*choose S = h.) - (c) If you delete vertex S, does the new graph G
_{0}- S have (S2) as its degree sequence? - (d) Use
*the method in the proof*to modify G_{0}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 G_{2} 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(v_{3}, v_{5}) in G_{3} from Homework I.

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

# BB1.

BB1. This concerns Theorem 1.1.2 and the example G_{0}. 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_{0}. 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).

- (a) In this example what are s, t
_{1}, ..., t_{s}, n, d_{1}, ..., d_{n}? (Give their values.) - (b) Label the vertices of G
_{0}by S, T_{1}, ..., T_{s}, D_{1}, ..., D_{n}as in the proof of the theorem.)**Do this problem for each of the three possible choices of S.** - (c) If you delete vertex S, does the new graph G
_{0}- S have (S3) as its degree sequence? - (d) Use
*the method in the proof*to modify G_{0}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.

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_{0} 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_{0}.

C5. In G_{2} 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_{3}, v_{5}) in G_{3} 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_{5}, 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.

- 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
_{2}back to v_{1}." 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.)

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_{3} 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).

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

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_{8}, 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.

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_{11}, 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_{1}, P_{2}, ..., 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).

See the corrections for Section 3.1.

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.

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.

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

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_{1}, P_{2}, ..., 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.

HH1. Use the proof method of Theorem 3.2.4 to decompose into subgraphs isomorphic to P_{3} :

- the Petersen graph, Fig. 1.1.13,
- the icosahedral graph I in Fig. 1.2.5,
- Fig. 2.3.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:

- the Petersen graph, Fig. 1.1.13,
- Fig. 2.3.6,
- Fig. 2.3.7,
- 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).

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_{7}, 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.

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

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

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

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_{8} 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.

**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_{6} - 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.

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

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_{5}), 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.

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

N1. Let N_{5} = {1,2,3,4,5}. Define a graph G_{5} by V(G_{5}) = the set of all unordered pairs ij of elements of N_{5}, with two pairs ij and kl adjacent if their intersection is empty.

(a) Prove that G_{5} 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 G_{2} 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.