Math 381: Graph Theory Announcements

Go to homework | course information | syllabus.

Tests

Test I (February 22 23)

This test covers HW I–V: everything we've done so far in the book (that's up to Section 2.2, inclusive) and the class. The guidelines for the grades are:

	A	B	C	D	F
	87-100	66-86	48-65	43-47	0-42

Test II (March 29)

This test covers HW VI–VIII (Sections 2.3-3.2). The guidelines for the grades are:

	A	B	C	D	F
	82-100	63-81	44-62	40-43	0-39

The points per problem are

1: 1	2: 10	3G: 15 (5+2+8)	3H: 15 (4+3+8)	4: 10	
5: 15 (10+5)	6: 12	7: 12	8: 10

Test III (May 3)

This test covers HW IX–XI (line graphs, automorphisms, Sects. 4.1-2, 8.1-3, and 9.1). The guidelines for the grades are:

	A	B	C	D	F
	78-100	60-77	42-59	38-41	0-37

Here is a solution sheet (complete) with discussion of the grading.

Final Exam (Mon., May 16, 4:30 - 6:30 p.m., in S2-145)

The final exam is comprehensive, but it will not test

infinite graphs (Section 3.3),
straight-line graphs (the latter part of Section 8.4),
knowing formulas for crossing number, thickness, and splitting number of K_n and K_m,n (end of Sections 9.1, 9.2),
empire graphs, earth-moon graphs (Section 9.3),
graphs.in the torus (Section 10.4),
straight-line graphs (in Section 8.4).

Do expect somewhat greater proportional emphasis on Sect. 9.2 than on earlier material.

The guidelines for the grades are:

	A	B	C	D	F
	112-150	82-111	52-81	45-51	0-44

Quizzes

Quiz 1 (April 15)

Quiz 2 (April 29): Takehome quiz, due Mon. 5/2.
It will not be graded. You should do your best and bring in your solved quiz on Monday.

Quiz 2 (May 2):
It is not graded; it's for discussion after the quiz.

Additions and Corrections to the Textbook

Additional Definitions
- The order of a graph is the number of vertices, |V(G)|.
  The size of a graph is the number of edges, |E(G)|.
- Let G and H be graphs. An isomorphism between G and H is a function f: V(G) to V(H) such that f is a bijection (one-to-one correspondence) with the property that, for v, w in V(G), vw is an edge in G if and only if f(v)f(w) is an edge in H. (Remark: That is what the book means on page 13 when it says the correspondence "preserves adjacency".)
  G and H are isomorphic if there exists an isomorphism. They are not isomorphic if no isomorphism exists.
  
  One kind of isomorphism is especially interesting. An automorphism of a graph G is an isomorphism of G with itself. Every graph has at least one automorphism, the identity automorphism, which is the identity function from V to V. Some graphs have no other automorphisms. Other graphs have many automorphisms. See the automorphisms handout (pdf).
- A separating set in G is a set of vertices whose removal leaves a disconnected. (Not an empty graph; there must be at least two components after deleting the separating set.)
  A disconnecting set in G is a set of edges whose removal leaves a disconnected graph.
- κ(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 κ(v,w), the connectivity between v and w, is the smallest number of vertices whose removal leaves v and w in different components.
- The complement of a graph G (i.e., a simple graph, not multi or pseudo) is supposed to be G with a bar over it. On the Web pages it is G^- (because I can't type G-bar properly in HTML).
- A clique in G is a set of vertices that are all adjacent. In a complete graph every subset of V is a clique. In any graph, a set containing just one vertex is a clique, and a set of two adjacent vertices is a clique, and in general a clique is the vertex set of a complete subgraph.
- The maximum degree of G is the largest degree of any vertex. The usual notation is Δ(G).
- A graph is called Hamiltonian if it has a Hamilton cycle.
- The line graph of G, written L(G), is the graph whose vertex set is V(L(G)) := E(G) and in which e, f (vertices of L(G)) are adjacent if and only if they are adjacent edges in G (that means they have a common vertex in G). The name comes from the fact that "line" is another name for "edge"; the line graph is the graph of edge adjacencies.
  See the line graphs handout (pdf).
- Embedding a graph in a surface (such as the plane or the sphere) means drawing it without self-intersections (the book says "without crossings" but they mean no self-intersections of any kind).
- A plane graph is an embedding of a graph in the plane. It is not a graph! A graph does not have regions. An embedding has regions, and what they are may depend on how the graph is embedded.
- In a plane graph, the degree of a region is the length of its boundary. This is sometimes greater than the number of edges, as an edge sometimes appears twice on the boundary.
- A plane triangulation is a plane graph in which every region is a triangle. Note that this is a property of a drawing of a graph, not of a graph.

In Exercise 1.1 # 7 you have to assume p ≥ 2. What goes wrong if p = 1?

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

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 same goes for # 5.)

In Exercise 2.1 # 15(a), the subgraph that is forbidden is K₃, not K₄.

Vizing's Theorem 2.2.2 is actually true of all graphs, not just regular graphs.

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 equivalent to the printed line, but the printed line doesn't follow the pattern it's supposed to.)

Problem 2.4.12 has a space with four underlines for the answer. This does not mean four words. It doesn't mean anything except a blank space.

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.

Exercise 3.3.17: The graph you find should also be connected, in addition to the other properties that are specified.

The order of a g-cage cannot be known in general but we can prove a lower bound. Here is the theorem for reference.
Theorem 4.2.A. A g-cage has at least b(g) vertices where
b(g) = 3 · 2^(g-1)/2 − 2, if g is odd,
b(g) = 2 · 2^g/2 − 2, if g is even.

For the chapters on planarity and surfaces, be sure to see the relevant definitions in the definitions list above.

Theorem G. If G is a planar graph and has girth g (where 3 ≤ g < infinity), then q ≤ [g/(g-2)](p-2).
This is a generalization of Theorems 8.1.3 and 8.1.5.
Exercise 8.2.6: Assume G is connected. (The problem is rather uninteresting if G is assumed to be connected.)

Definition for Exercise 8.3.7: A plane triangulation is a plane graph in which every region is a triangle. Note that this is a property of a drawing of a graph, not of a graph.

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.

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.

The definition of stretchability after Theorem 8.4.1 is for graphs. There is a similar definition for a plane drawing of a graph. A plane drawing is called stretchable if the edges in the drawing can be straightened (the vertices can be shifted around if necessary) without introducing any forbidden intersections in the straightening process.

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

The proof of Theorem 9.1.4 should consider the possibility that the two quadruples intersect in more than two vertices. (It is not hard to fix the proof.)

Theorems 9.2.1 and 9.2.2 require the assumption that p ≥ 3.

The lower bound
(1) θ(K_n) ≥ floor[(n+7)/6]
stated on p. 192 should be
(2) θ(K_n) ≥ ceiling[(n+2)/6].
(1) and (2) are mathematically equivalent, but (1) is lengthy to prove and (2) is easy and short.

In Figure 9.2.4 there are three duplicate edges. (Can you find them? This doesn't invalidate the proof that σ(K₉ ≤ 6.)

Note that Exercise 9.3.2 uses only the easy half of Theorem 9.2.4.

(Supplement to Chapter 9.) Here are some useful general theorems based on Theorem G.
- Theorem CR. If G is a graph (not necessarily planar) and has girth ≥ g, and if p ≥ 3, then
  cr(G) ≥ q - [g/(g-2)](p-2).
- Theorem TH. If G is a graph (not necessarily planar) and has girth ≥ g, and if p ≥ 3, then
  θ(G) ≥ (g-2)/g · q/p.
- Theorem SPL. If G is a graph (not necessarily planar) and has girth ≥ g, and if p ≥ 3, then
  σ(G) ≥ [(g-2]/g] q - (p-2).
(Most of these are homework problems to prove.)

On page 208, the definition of a rotation of a graph doesn't need the degrees to be 3. They can be anything, as the book says later on.

On page 209, "each direction in at least one" should be "each direction in exactly one".

Note that the two definitions of a rotation of a graph, on page 208 for a cubic graph and pages 212–213 for any graph, are really equivalent.

Figure 10.3.10 is missing the currents on the edges.

In Theorem 10.3.7 the ceiling function should be the floor function.

In Theorem 10.3.8, "and γ(G) ≤ g" should be "with γ(G) ≤ g".

The sphere with γ handles is written T_γ (by some people). T₁ is the torus, T₂ is the double torus, etc..
- Here are pages with diagrams for T₁ (the torus) and T₂ (the double torus), or both T₁ and T₂, that you can use for drawing graphs.
- You can apply Theorem T to get an idea of whether a given graph G can be embedded in a given surface. Specifically, look for a lower bound on the number of handles, similar (in a very general sense) to the lower bounds for thickness, crossing number, and splitting number. The actual smallest number of handles needed to embed G is the genus of the graph G, written γ(G).
- Use that lower bound to get an idea of which complete graphs K_n or complete bipartite graphs K_m,n can be embedded in a given surface T_γ. Specifically, look for a lower bound on the number of handles, and then find an embedding using only that many handles, if you can! (The lower bound theorems are stated in Sect. 10.3, but their proofs are very technical.) Try the torus, and if you're ambitious, try the double torus. The results get cute.

Extra Problems

For thinking about.

* This problem concerns the average degree and the number of cycles in a simple graph G. (The average degree is simply the average of all degrees.)
1. Suppose the average degree is > 2.
  1. Prove that G has at least 2 cycles.
  2. Also prove that this is the best possible number: G could have exactly 2 cycles.
2. Suppose the average degree is 3 and G is connected.
  1. Show that G has at least 4 cycles.
  2. Is 4 the best possible number, or is it possible to prove that G has at least 5 cycles? At least 6?
  3. What is the largest number k such that a graph G of this type has to have at least k cycles?
3. You may also vary the problem. What if G is disconnected? What if the average degree is ≥ 3? Do these changes affect the answer?

* If G is a cubic graph, is it possible to partition the edges into paths whose average length is 3?

* Suppose G is a simple graph of order n that contains exactly one triangle. What is the largest possible number of edges in G? (NOTE: To do this problem you should first understand Exercise 5.10. You don't have to be able to prove it, but you should know which graph it is that gives the k² edges.)
1. n = 10.
2. Any value of n.

* Find the largest number of edges in a simple graph G of order n ≥ 3 that has no even-length cycles.

* Suppose T is a tree. Define T' to be T with all end vertices removed. If x is a vertex of T, then T - x has k components, which I will call T₁, ..., T_k. (Therefore, k = 1 if x is an end vertex, k = 0 if x is the only vertex, and otherwise k ≥ 2.) For each i = 1, ..., k, define D_i(x) = max dist(x,u) over all vertices u in T_i.
Now here is the problem: prove (or disprove) the following theorem.
Theorem: The following statements about a tree T and a vertex x of T are equivalent.
1. x is a center of T.
2. x is a center of some longest path in T.
3. x is a center of every longest path in T.
4. x is a center of T' (in this, assuming n ≥ 3).
5. All D_i(x) (for i = 1, ..., k) differ by at most 1 (here, assuming deg(x) ≥ 2).
If any part of this theorem is not true, try to find a correct statement.

Go to homework | course information | syllabus.