Math 381: Graph Theory Announcements

Tests

Test I (February 20)

[This test covers everything we've done from the book and class in Sections 1-8 except digraphs, Section 4, and the Chinese postman problem in Section 8. (Section 4 and the Chinese postman problem will not be tested in the course.) You do not need to memorize the Platonic graphs or their names. I do expect you to know K_n and Q_k, of course.] The guidelines for the grades are:

	A	B	C	D	F
	83-100+	67-82	51-66	41-50	0-40

Test II (March 27)

[This test covers what we've done from Sections 9-13, except Sections 11 and 14. (Sections 11 and 14 will not be tested in the course.)] The guidelines for the grades are:

	A	B	C	D	F
	86-100	74-85	58-73	50-57	0-49

Test III (May 1)

This test covers what we've done from Sections 15-20, but Sections 11, 14, and 21 will not be tested. (Section 21 will be tested on the final exam.) [Oops! I did test 21 on Test III. My mistake; my apologies. Fortunately, it seems that no one believed me.] The guidelines for the grades are:

	A	B	C	D	F
	80-100	64-79	46-63	36-45	0-35

Final Exam (Wed., May 14 at 8:30 a.m.)

The final exam is comprehensive. It covers everything we've covered in class except Sections 4, 8, 11, and 14 and the extra stuff (acyclic orientations; proving one version of Menger's theorem from another version). It will give extra emphasis to Section 28 but most of the test will be on the other parts of the course.

The guidelines for the grades are:

	A	B	C	D	F
	118-150	95-117	71-94	58-70	0-57

Additions and Corrections

``Graph''

In many problems (and theorems) the word ``graph'' has to be interpreted as ``simple graph''. I will try to point these out but I won't find all such places. If in doubt, ask me.

In Exercise 1.5, the maze should have another identifying letter, say N, at the tail of the arrow pointing to L.
In Exercise 3.5(v) (p. 20), the graph should be simple and the K₄ should be K₅.
Definition of path (pp. 3-4 and 26-27): On pp. 26-27, the book defines a path as being either open (that means ``not closed''!) or closed. However, on pp. 3-4, it defines a path as being open. Also, when it uses paths it almost always means open paths. (Just one big example: in Theorem 9.1, which would be false if we allowed the paths to be closed.)
When I say ``path'' I always mean ``open path''. Thus for me (and for the book, mostly) a ``closed path'' does not count as a ``path'' (weird, isn't it!).
Of course, we all agree that a closed path is the same as a cycle.
If you read very carefully on p. 29, you'll notice that in talking about the connectivity, that is, kappa(G), we always assume G is connected. However, in talking about the edge connectivity, lambda(G), we do not assume G is connected.
Exercise 5.8: You must assume the graph is simple.
Exercise 5.9(i): The vertex z must be different from v and w.
Theorem 6.2: The easy half is due to Euler (1736). The hard half is due to Hierholzer (1873) (who died young; his article was written down after his death by friends).
Exercise 6.4: G can have any number of vertices. The number that have odd degree is k (a positive number).
Corollary 7.2 (Dirac's Theorem): The statement should say ``deg(v) >= n/2'', not ``deg(v) > n/2''.
Exercise 7.7: In (i) assume G is simple. (If G is not simple, is the statement still true?) In (ii) your graph should be simple.
The algorithm for shortest path on p. 39 is usually called Dijkstra's Algorithm. The algorithm is not stated completely in the book. In order to be able to recover the shortest paths from the starting vertex, you have to record, each time you change the number at a vertex, the edge you used to calculate the new number.
P. 44 (bottom): In the discussion of the existence of (at least) two end vertices of a tree with n vertices, the condition ``n > 2'' should be ``n >= 2''.
Theorem 10.1, first proof: For a complete proof it is also necessary to prove that, if you begin with a sequence and find the tree, then find the sequence associated with that tree, you always get the original sequence.
P. 50, top formula: (n-1)_n-k-1 should be (n-1)^n-k-1. Also, the symbol ( n-2 over k-1) (impossible to type in HTML) is the binomial coefficient. You should be familiar with this from calculus (Hint! look it up in your calculus book.), but here is a definition for q > 0:
( p over q ) = p(p-1)···(p-q+1) / q! .
For q = 0, we define ( p over 0 ) = 1.

Exercise 10.3: ``the number of labelled trees''.

Exercise 10.5(i): The edge e must not be a loop.

In Theorem 13.7, the second formula is really just a disguised form of the first one. You can safely ignore the second formula.

Exercise 13.10 has two errors. (i) has a minor error: it is not valid if r + s = 2 (that is, r = s = 1). (ii), first part, is completely wrong: the ``= r'' should be ``<= r/2''.

In Exercise 14.1, the vertical arrows are different from the horizontal arrows. The vertical arrows should be drawn as double arrows.

In Figure 15.1, one of the edges that should have been dotted was printed solid by mistake.

The proof of Corollary 15.4 requires that one assume G is connected.

Exercise 17.9 may be hard to interpret. I understand what Wilson means in (i) but not in (ii). Here are good versions of the questions.

In 17.8 replace the condition that G has no triangles by the condition that G has girth r. In the modified 17.8(i) prove that G has a vertex of degree at most d, where d is a number that you are supposed to figure out for yourself in such a way that the new result is interesting and worthwhile. In the modified 17.8(ii) the number of colors, 4, would be replaced by a number that you figure out for yourself, keeping in mind that the method used to prove it is probably similar to that used in 17.8(ii).
Replace the condition that G is planar by the condition that G has thickness t. (It makes no sense to keep the condition that G is planar. If you did, there would be no point in talking about thickness.) Keep the condition that G has no triangles. Or maybe, don't keep that condition; just keep the assumption that G is simple. Thus you have two versions of this question; you may solve either or both, or further variants if you find interesting ones. Again, in whatever problem you come up with, there are two parts corresponding to the two parts of 17.8, but they may not be identical to those in 17.8. You are supposed to figure out how to modify 17.8 here, just as in 17.9(i).

In Exercise 17.11, all k-critical graphs are simple. Also, as usual, you should prove the correctness of your answers.

Maps: In Figure 19.5 the ``map'' is not 3-connected so it isn't really a map according to the book's definition. You can fix it by adding an edge from the left vertex to the right vertex around the top of the figure.
(N.B. Many books define a map as a plane graph that is connected and has no bridges. Then Figure 19.5 would be a map.)

In Exercise 21.7(i), the formula should be k(k-1)^n-1.

In Exercise 25.5, you should assume G is not a null graph.

Corollary 28.4 should say ``any two distinct non-adjacent vertices''.

Theorem 28.7. The maximum number of internally disjoint paths from vertex v to vertex w in a digraph is equal to the minimum number of vertices in a vw-separating set. (See definitions.)

In Exercise 28.2(i), there is nothing to verify for Theorem 28.2 because the theorem applies only to nonadjacent vertices. Watch out for the same problem in any similar exercise.

Connectivity

There should be some additional results stated in the book, to make it clearer what connectivity means. We discuss this in class, with some proofs. You should study that (at the appropriate time). Here are the theorem and corollaries. In them, G is a connected graph.

Theorem. G is p-connected if and only if no set of fewer than p vertices can separate G. (Assuming p > 0.)
Corollary. If G is (p+1)-connected, then it is p-connected. (Assuming p > 1.)
Corollary. If kappa(G) = p, then G is p-connected but not (p+1)-connected.
Examples.

G is 1-connected iff it is connected.
G is 2-connected iff it has no cut vertex.

Definitions

The order of a graph is the number of vertices, |V(G)|.

P_n is the name for the path graph of order n (that is, length n-1).

A Hamiltonian path in G is a path (that is, open path) that contains all the vertices of G. (Note that if there is a Hamiltonian cycle, there must be a Hamiltonian path, but it is perfectly possible for a non-Hamiltonian graph to have a Hamiltonian path.)

[Optional] A clique in a graph G is a set of vertices that are all adjacent to each other.

[Optional] An independent set in G is a set of vertices of which none is adjacent to any other.

[Optional] The clique number, omega(G), is the largest size of a clique in G.

[Optional] The independent set number, alpha(G), is the largest size of an independent set of vertices in G.

[Optional] The unoriented incidence matrix M_G is the matrix defined in the book. The oriented incidence matrix N_G is similar, but in the column of each edge you put one 1 and one -1 instead of two 1's.

A matching in a graph G is a set of edges of which no two are adjacent (that is, there are no two edge in the matching that share a common vertex). A perfect matching in G is a matching such that every vertex of G is an endpoint of some edge in the matching.

On page 122, Wilson defines vertex-disjoint paths. A better name for this, found in most sources, is internally disjoint paths. I prefer the latter, but we can use either name.
Definitions for Sects. 22, 28: In a digraph D with vertices v,w in V(D), a vw-separating set is a set of vertices, X subset of V(D), such that v, w not in X and D - X has no path from v to w. (That means directed path, since D has directed edges.) A vw-disconnecting set is a set of edges, B subset of A(D), such that D - B has no path from v to w.

Extra Problems

For thinking about. Some could make term papers (*).

Take a small simple graph G and calculate M_G (the incidence matrix), A_G (the adjacency matrix), A_L(G) (the adjacency matrix of the line graph), M_GM_G^T, and M_G^TM_G. (M^T means the transpose of the matrix M.) Compare your answers.
Do the same with the oriented incidence matrix N_G. (See definition above.)
* Prove a theorem about the relationships among M_G (the incidence matrix), A_G (the adjacency matrix), A_L(G) (the adjacency matrix of the line graph), M_GM_G^T, and M_G^TM_G. (M^T means the transpose of the matrix M.)
* Do the same with the oriented incidence matrix N_G. (See definition above.)
* Find a formula for the rank of the matrix in terms of properties of G:
1. M_G
2. N_G
* Find and prove theorems and corollaries to clarify edge connectivity in a way analogous to the discussion of connectivity (above).
* Let G' denote the complement of a simple graph. (I can't type G-bar properly in HTML.) Prove the theorem: If G and H are simple graphs, then G is isomorphic to H if and only if G' is isomorphic to H'.
* 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. Definition 1. I define T' to be T with all end vertices removed. Definition 2. 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 d(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.