Math 381: Graph Theory Announcements


Go to homework | course information.

Special Office Hours MAYBE:

Sunday, May 9: I expect to be around my office during the afternoon OR evening; I don't know exactly when, but feel free to call or stop by.

Tests

Test I (February 19)

This test covers everything we've done so far in the book (that's up to Section 2.1, inclusive) and the class (including Menger's Theorems).

The points per problem are:

	A	B	C	D	E	F	G	H
	10	15	10	5	15	15	15	15

The guidelines for the grades are:

	A	B	C	D	F
	81-100	62-80	43-61	35-42	0-34

Test II (March 25)

This test covers Sections 2.2-3.3. The guidelines for the grades are:
	A	B	C	D	F
	78-100	61-77	43-60	34-42	0-33

Test III (April 29)

This test covers Sects. 4.1-2, 8.1-4, and 9.1, except for whatever we've skipped in the assignments. The guidelines for the grades are:
	A	B	C	D	F
	77-100	60-76	43-59	36-42	0-41

Final Exam (Mon., May 10, 11:00 a.m. - 1:00 p.m., in S1-140)

The final exam is comprehensive, but it does not test Section 9.3. Do expect somewhat greater emphasis on Sect. 9.2 than on earlier material.

The guidelines for the grades are:

	A	B	C	D	F
	120-152	99-119	72-98	65-71	0-64

For solutions of those two pesky problems on the splitting number of P, the Petersen graph, and the relationship between thickness and crossing number, click on the links (or scroll to the bottom). There's also a remark about the degree-sequence problem.


Additions and Corrections to the Textbook


Solutions to the hard problems on the final exam:

#2: Degree sequence of a tree? This is easy: draw a tree. But is it true, as many people assumed, that if the sequence implies there are 8 edges and 9 vertices, that it is the degree sequence of a tree and you need not do further checking?

In general, take a sequence of p integers whose sum equals 2(p-1). Is it necessarily the degree sequence of a tree? No, for two reasons: (1) it may not be graphic at all, and (2) even if it is, it can't be a tree sequence if it has 0's in the sequence (unless p=1). But if it is graphic and it has no 0's, I don't know the answer! Watch this space for more info.

#10: Splitting number of P. It's easy to prove the number is at most 2 and at least 1. To prove it isn't 1, by contradiction: suppose it is 1. That means splitting one vertex once makes P planar. Think about how to split one vertex, v, in a cubic graph like P: you must split one edge from two others; so the vertex splits into v (of degree 2) and v' (of degree 1). Call the split graph P'; it's planar. Therefore the graph you get from P' by deleting v' (and its one edge, e) is planar; call this P". But wait! P" = P-e. That is, P-e would have to be planar, for some edge e. There are several ways to prove that is impossible. The easiest would be to use the girth bound: P-e has girth 5 and 14 edges, so if it is planar, then 14 <= (5/3)(10-2) = 13.333..., a contradiction. Another way is to apply Kuratowski's method to prove each P-e is nonplanar, using symmetry to reduce the number of edges you have to check.

#11: Thickness and crossing number. Let's look at a graph G. Draw it with the minimum number of crossings: that's cr(G) crossings. Remove one edge from each crossing, leaving a graph G0 which is planar because it's drawn with no crossings. You removed c edges where c <= cr(G). (Possibly not equal, because one edge might have been in multiple crossings; but this doesn't matter.) Now, divide up the c removed edges into sets of 8, with any leftovers going into a last set; the number of sets, n, is = ceiling(c/8). Each set makes a graph with at most 8 edges, which is planar because it can't contain a subdivided K3,3 or K5. Thus, with G0 and these n subgraphs you have decomposed G into 1+n planar subgraphs, which is <= 1 + ceiling(cr(G)/8). Thus, the thickness is <= 1 + ceiling(cr(G)/8).


Go to
homework | course information.