Math 510
Introduction to Graph Theory
Spring 2014

Syllabus and Assignments

Index

• Ch. I.
• Ch. II.
• Ch. III.
• Ch. IV.
• Ch. IX.
• Ch. VIII.

This is the syllabus plus homework assignments.
    On proofs: You must use only what has been done in this book in the current and previous chapters. Cite all results from the book that you use.

    Summer homework submissions: All homeworks submitted after Fri. 5/16 (the official deadline for HW G) are considered rewrites (even if your first submission). I will accept them up to mid August, i.e., they have to be graded before the Fall term begins. There are no particular deadlines for these submissions but don't postpone them; delay begets delay.

• 1/26 – 2/3
  Introduction to graph theory. (Alex Schaefer)
  
  
• 2/5 – 2/26
  Chapter I: Graphs and Subgraphs. (with Vaidy Sivaraman)
  • Description: Basics.
  • HW A, due Wed. 3/5:

    Read Ch. I and Sects. II.1–2.

    Hand in ## I.1 – I.3 and I.5 – I.7.

    First rewrites are due Wed. 4/30.
  • # I.5. Prove

    Theorem I.T1 (Tree Paths). A graph is a tree if and only if for any two vertices, there is one and only one path between them.

  • # I.6. Prove

    Theorem I.T2. A graph G is a tree if and only if it satisfies any two of the following three conditions.

    1. G is connected.
    2. G contains no circuits.
    3. |E| = |V| − 1.

  • # I.7. We use a method of generating all trees of order n, T_n, by taking a tree T_n−1, adding a new vertex v_n, and adding an edge joining this vertex to any one vertex of T_n−1.
      Write a complete proof that this method, starting with T₁ = K₁, generates all trees and only trees.
  • # I.8. A denotes the adjacency matrix of G. Prove

    Theorem A. For m ≥ 0, (A^m)_ij is the number of walks of length m from v_i to v_j.

• 2/26 – 3/13
  Chapter II: Contractions and the Theorem of Menger.
  • Description: More basics; and famous theorems.
  • HW B, due Wed. 3/12:

    Read Ch. II.

    Hand in ## II.1, II.8 – II.12.

    First rewrites are due Thurs. 5/15.
  • # II.7. Prove König's theorem directly from Menger's theorem (Theorem II.35).

    König's Theorem. Let G be a bipartite graph with bipartition (U, V). The largest size of a matching (i.e., partial 1-factor) equals the smallest size of a vertex cover (a set X of vertices such that every edge has at least one endpoint in X).

  • # II.8. Assume G is connected and let T be a spanning tree. I defined the fundamental circuit of an edge e not in T, with respect to T, written C_T(e). Prove that every circuit is the set sum (symmetric difference) of fundamental circuits with respect to T. (For this problem and the following we consider a circuit as an edge set.)
  • # II.9. Suppose you have a set of circuits that generates all circuits by set addition. Prove there are at least p₁(G) circuits in your set.
  • # II.10. Suppose you have a minimal set of circuits that generates all circuits by set addition. Prove there are exactly p₁(G) circuits in your set.
  • # II.11. How is the theorem of #II.10 related to bases in vector spaces? This is not a proof question!
  • # II.12. [Optional, as it's a theorem in the chapter.] Prove (or disprove): For every cutting pair (H,K), w(G;H) ≥ λ(G;P,Q).
  • # II.13. Restate Theorem II.38 in terms of the maximum size of a partial 1-factor, and prove your restatement (you may use Theorem II.38).
      Note on terminology: Many people call a 1-factor a "matching" and a partial 1-factor a "partial matching. Many call a 1-factor a "perfect matching" and a partial 1-factor a "matching". (!)


• 3/13 – 3/21
  Chapter III: 2-Connection.
  • Description: Basic structure theory.
  • HW C, due Wed. 3/26:

    Read Sects. III.1–3.

    Hand in ## II.2 – II.4, II.6, II.7, II.13, and III.5.

    First rewrites are due the first class after the break, Wed. 4/22.
  • # III.4. Prove the following "vertex" version of Theorem III.7.

    Theorem III.7v. Let G be an inseparable graph and let U, V be nonnull vertex sets in G. Then μ_G(U,V) ≥ 2 with these exceptions: when U = V and |U| = 1, or when G = K₂ (or just possibly one or two other exceptional cases that I missed).
      [Correction 5/4] The theorem should have read: Then μ_G(U,V) ≥ 2 with some exceptions. Find the exceptional cases.

  • # III.5. Assume G is connected. Prove that a vertex v is a cutpoint if and only if it has more than one bridge.


• 3/24 – 4/25
  Chapter IV: 3-Connection.
  • Description: Higher structure theory.
  • HW D, due Wed. 4/9:

    Read Ch. III (if you haven't finished it) and Sects. IV.1–4 (Sect. 4 is needed for 4/7).

    Hand in ## III.1 – III.4, IV.1, IV.2, IV.3(i).

    First rewrites are due Fri. 5/2.
  • HW E, due Fri. 4/25:

    Read Sects. IV.5–7.

    Hand in ## IV.4 – IV.6 and IV.8 – IV.10.

    First rewrites are due Thurs. 5/15.
  • # IV.8. Prove that in an n-connected graph G, all vertex degrees are at least n.
        (a) For Tutte n-connection. Assume G has at least 4 edges. Is it necessary to assume G has at least 2n-1 edges?
        (b) For verticial n-connection. Assume G has at least 4 vertices. How can you fit complete graphs into this?
  • # IV.9. Prove that if G is inseparable, then subdividing an edge gives an inseparable graph.
  • # IV.10. Let G be 3-connected. I claim that (Big-Circuit Vertex Expansion) when expanding a vertex x of degree k into a circuit C_j so as to get another 3-connected graph, if you're allowed to duplicate edges at x, then you can allow j to be as large as you like instead of bounded by k.
        (a) Prove that.
        (b) Is it possible to deduce Big-Circuit Vertex Expansion from Tutte's circuit vertex expansion and his other 3-connection-preserving operations? Give me your thoughts on this, and a proof if you can prove something (anything!).


• 5/1 – 5/15
  Chapter IX: Polynomials Associated with Graphs. (with Vaidy Sivaraman)
  • Description: Algebra of deletion-contraction invariants. Chromatic number and chromatic index. Line graphs.
  • HW F, due Tues. 5/13 – Thurs. 5/15 Fri. 5/9:

    Read Sects. IX.1–2, 4, 6.

    

    Hand in ## IX.1, IX.2 for the graph G₂ at the right G in Fig. II.2.1, IX.3, IX.7 – 13, IX.15. Hint for IX.2: Think of easier ways than slogging through the definition of Q_G2. (By the way, Vaidy thinks Tutte meant III.2.1 and III.2.2.)

  • Terminology: Tutte's "dichromate" is known to the rest of the world as the "Tutte polynomial". It has become very popular.
      Don't confuse the Tutte polynomial ("dichromate") with the dichromatic polynomial. The Tutte polynomial generalizes to matroids. The dichromatic polynomial is essentially graphic, like the chromatic polynomial.
  • Regarding chains we had several results. Recall that
    • R is a commutative, unital ring, usually Z or Z_m;
    • Cⁱ(G; R) is the set of i-chains on G and it is an R-module;
    • a Z-module is the same as an abelian group (just by comparing the definitions);
    • the coboundary operator is δ : C⁰(G; R) → C¹(G; R) defined by δh(uv^→) = h(v) − h(u) for h ∈ C⁰(G; R) (here uv^→ is the edge uv oriented from u to v). The functions δh are called 1-coboundaries of G. The set of 1-coboundaries is B¹(G; R).
        (N.B. to people in algebraic topology: The graph theory terminology is mixed up. The mapping goes up, hence "co-", and it acts on cochains, which Tutte calls "chains" because in graph theory we treat chains and cochains as the same thing. I mistakenly wrote the "chain" groups with subscripts here, which I've changed to superscripts. Try not to notice the confusion.)
    Now here are the homework problems:
    • # IX.8. A chord of a circuit is an edge that joins two nonconsecutive vertices of the circuit. Prove:

      Theorem IX.C1. A 1-chain f of G (over the ring R) is a coboundary
      ⇔ the sum of f(e) on each circuit is 0, where the edges of a circuit Z are oriented consistently around Z
      ⇔ the sum is 0 on each chordless circuit.

      [N.B. I could have added two equivalences: ⇔ the sum is 0 on each fundamental circuit with respect to some maximal forest; also, every maximal forest.]
    • # IX.9. Prove

      Theorem IX.C2. For two 0-chains h and h', δh = δh' ⇔ h' − h is constant on each component of G.

    • # IX.10. Prove

      Corollary IX.C2A. Let R have finite order k. Then δ is a k^p₀(G)-to-1 function from C⁰(G; R) to B¹(G; R).

    • # IX.11. Prove

      Corollary IX.C2B. The number of nowhere-zero coboundaries is P_G(k)/k^p₀(G). (P_G(k), also written χ_G(k), is the chromatic polynomial.)

  • The reliability polynomial Rel_G(p) of a connected graph G is defined as the probability that a random spanning subgraph is connected, if each edge of G is deleted with probability p. Here p is any constant number in [0,1]. We say a deleted edge has failed; we think of it as breaking, leaking, burning out, or something like that. Thus Rel_G is the probability that the network remains connected given the probability p of failure of each edge. The next problems concern reliability. You may use the basic formula

    Rel_G(p) = ∑_S p^|S| (1−p)^|E|-|S|

    where S ranges over all edge sets of connected spanning subgraphs of G. [fixed May 15]
    • # IX.12. Prove that

      Rel_G(p) = (1−p)^|E| v Q^{^}_G(p/(1−p), v)|_v=0,

      where Q^{^}_G(λ, v) := Q_G(λ/v, v), i.e., λ = uv. [Two minor errors fixed May 20. There is still something wrong with it but (May 24) I'm sure it can be made correct with some adjustment. Can you find that adjustment?]
    • # IX.13. Use its definition to prove that (in general) Rel_G is is not changed by simplifying G if G was not simple. The best answer would characterize exactly what simplifications of which graphs leave Rel_G unchanged; the simplest answer would show that there exist graphs for which the reliability polynomial is changed by simplification. Intermediate levels of generality are intermediately good.
    • # IX.14. Use any of the preceding properties of Rel_G to deduce that it satisfies a slightly modified deletion-contraction relation.
  • For the next problems, define the polynomial π_G(κ) by the formula

    π_G(−(λ−1)) := (−1)^n−p₀(G) P_G(λ)/λ^p₀(G).

    (Here n := |V(G)|.) We define the empty graph to have 0 components. Then write π_G(κ) = ∑_i π_i κⁱ, so the π_i are the coefficients in π_G(κ). (They are closely related to Tutte's U_i, but not identical.)
    • # IX.15. Prove that π_G(κ) satisfies the deletion-contraction relation for every edge that is neither an isthmus nor a loop.
    • # IX.16. Prove that π_G(κ) satisfies the multiplicative relation for a disjoint union of graphs.
    • # IX.17. Deduce from IX.15–16 that all coefficients of π_G(κ) are nonnegative.
    • # IX.18. Express the coefficients of the chromatic polynomial in terms of those of π_G(κ).
  • # IX.19. Compute the Tutte polynomial of G₂ using the spanning-tree formula and activities. Is your result consistent with your dichromatic polynomial from # IX.2?
  • # IX.20. Compute the chromatic polynomial of the graph H = K_n with the edges of a path of length 4 removed (n ≥ 5 4 is too small).
  • # IX.21.
    1. Compute the flow polynomial of an n-circuit. Compare to the chromatic polynomial of an n-linkage.
    2. (No-credit challenge) What would you expect the flow polynomial of an n-linkage to be?


• — (no classes on this chapter)
  Chapter VIII: Algebraic Duality.
  • Description: Algebraic approach to graph structure.
  • HW G, due Fri. 5/16:

    Read Sects. IX.3, IX.5, and VIII.1. Also read the first page of Sects. VIII.4–5. In Chapter VIII concentrate on the definitions, explanations, and theorems, not the proofs. You'll find some of it is familiar from lectures.

    Hand in ## IX.19 – 21.

To the main course page.
To my home page.