Math 381: Graph Theory Announcements


Go to homework | course information.

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 Kn and Qk, 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

Definitions

Extra Problems

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

  1. Take a small simple graph G and calculate MG (the incidence matrix), AG (the adjacency matrix), AL(G) (the adjacency matrix of the line graph), MGMGT, and MGTMG. (MT means the transpose of the matrix M.) Compare your answers.
  2. Do the same with the oriented incidence matrix NG. (See definition above.)
  3. * Prove a theorem about the relationships among MG (the incidence matrix), AG (the adjacency matrix), AL(G) (the adjacency matrix of the line graph), MGMGT, and MGTMG. (MT means the transpose of the matrix M.)
  4. * Do the same with the oriented incidence matrix NG. (See definition above.)
  5. * Find a formula for the rank of the matrix in terms of properties of G:
    1. MG
    2. NG


  6. * Find and prove theorems and corollaries to clarify edge connectivity in a way analogous to the discussion of connectivity (above).

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

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


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

  10. * 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 k2 edges.)
    1. n = 10.
    2. Any value of n.


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

  12. * 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 T1, ..., Tk. (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 di(x) = max d(x,u) over all vertices u in Ti.

    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 di(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.