Math 381: Graph Theory
Spring 2013
Announcements

Go to announcements | homework | course information | syllabus.

Extra Problems

For thinking about and possible term papers (*).
  1. * 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?

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

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

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

  5. * 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 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 dist(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.