Go to homework | course information.

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

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

A B C D F 78-100 61-77 43-60 34-42 0-33

A B C D F 77-100 60-76 43-59 36-42 0-41

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.

- The
*order*of a graph is the number of vertices, |V(G)|. - The
*size*of a graph is the number of edges, |E(G)|. - A
*separating set*in G is a set of vertices whose removal leaves a disconnected or empty graph. (Thus, V is a separating set in every graph, but it need not be a minimal separating set.) - A
*disconnecting set*in G is a set of edges whose removal leaves a disconnected graph. - kappa(G), the
*connectivity*of G, is the smallest number of vertices whose removal makes G disconnected or empty. - In a graph G, take two nonadjacent vertices v and w. Then kappa(v,w) is the smallest number of vertices whose removal leaves v and w in different components.
- lambda(G), the
*edge connectivity*of G, is the smallest number of edges whose removal makes G disconnected. - In a graph G, take any two vertices v and w. Then lambda(v,w) is the smallest number of edges whose removal leaves v and w in different components.
- G
^{-}is the complement of G, if G is a graph (i.e., simple, not multi or pseudo). (I can't type G-bar properly in HTML.) - 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." **Theorem 2.2.4**is valid only for n >= 2.- The graph I in
**Figure 1.2.5**is the one without a label. (It's the icosahedral graph.) - The graph of
**Figure 2.1.5**is not critical. That of**Figure 2.1.6**is critical. (You should prove these statements!) - 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 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.) **Section 3.1**: The definitions of**path, closed path, and cycle**are rather muddled. A*path*is a trail in which no vertex is repeated. A*closed path*is a closed trail (a circuit) in which no vertex is repeated except for the terminal vertex. Therefore a ``closed path'' is not a path! Sorry, that's the way it is.A trail is

*open*if it is not closed. An*Eulerian trail*in a pseudograph is a trail that contains every edge of the pseudograph. An*Eulerian circuit*in a pseudograph is a circuit that contains every edge of the pseudograph. Vertices need*not*be included in an Eulerian trail or circuit, despite what the book says on page 55.**Theorem 3.1.1 (corrected).**If a pseudograph G has an Eulerian circuit, then G is connected (except for isolated vertices) and the degree of every vertex is even.**Theorem 3.1.6 (corrected).**Let G be a pseudograph.

(a) G has an Eulerian trail if and only if it is connected (except for isolated vertices) and has*at most*two vertices of odd degree.

(b) G has an*open*Eulerian trail if and only if it is connected (except for isolated vertices) and has*precisely*two vertices of odd degree.**Exercise 3.1.1.**Find*an*Eulerian circuit---it need not be unique!**Exercise 3.1.13.**You need to assume that G is connected.- Definition for
**Exercise 8.3.7**: A*plane triangulation*is a plane graph in which every region is a triangle. **Exercise 3.3.17**: The graph you find should also be connected, in addition to the other properties that are specified.**Exercise 8.2.6**: Assume G is connected.**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).**Sect. 9.1, p. 180**: A*simple drawing*must also satisfy

d) no edge passes through any vertex.**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. - 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. I'll go over this in class. **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**p. 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.) **Theorem L**(see Problem Sets L and M) is: If G is a planar graph and has girth g (where 3 <= g < infinity), then q <= [g/(g-2)](p-2).

**#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 G_{0} 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 K_{3,3} or K_{5}. Thus, with G_{0} 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.