Math 381: Graph Theory Announcements

Tests

March 7 and April 25.
Final exam on Tuesday May 14.

Test I

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, both of which 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
	82-100	65-81	47-64	40-46	0-39

Test II

This test covers what we've done from Sections 9--20, but Sections 11, 14, and 21 will not be tested. (Section 21 will be tested on the final exam.) The guidelines for the grades are:

	A	B	C	D	F
	75-100	58-74	39-57	32-38	0-31

Final Exam

Review Session: Monday May 13, 2:30-4:00, in SW 313.

The final exam is comprehensive. It will cover 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).

The guidelines for the grades are:

	A	B	C	D	F
	110-150	80-109	52-79	42-51	0-41

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.

Connectivity

There should be some additional results stated in the book, to make it clearer what connectivity means. We discussed this in class, with some proofs. You should study that. 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.

Definition of path (pp. 26-27): The book defines a path as being either open or closed. However, 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.

Exercise 5.8(ii) is not stated correctly.

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

Corollary 7.2 (Dirac's Theorem): The statement should say ``deg(v) >= n/2'', not ``deg(v) > n/2''.

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.

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: ( p over q ) = p(p-1)···(p-q+1) / q! .

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 Figure 15.1, one of the edges that should have been dotted was printed solid by mistake.

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.
1. 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).
2. 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.
In Exercise 25.5, you should assume G is not a null graph.
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.

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.