Math 510
Introduction to Graph Theory
Spring 2022

Homework Assignments

On proofs: You must use only what we have done in this book in the current and previous chapters. Cite all results from the book that you use. I mean all.

• Chapter I: Graphs and Subgraphs.
  HW A, due W 2/9: Hand in ## I.1 – I.3.
  HW B, due M 2/21: Hand in ## I.1' and I.2'. (They are theorems that are not in our book.)
  • # I.1'. Prove that 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.2'. Let A denote the adjacency matrix of G. Prove that for m ≥ 0, (A^m)_ij is the number of walks (see the dictionary page) of length m from v_i to v_j.
  • # I.3'. Prove this essential Arc Connection Theorem. Distinct vertices a and b are in the same component of G if and only if there is an arc that joins them. Hint: See Theorem I.43.


• Chapter II: Contractions and the Theorem of Menger.
  HW C, due M 2/28: Hand in ## II.1, II.2, and II.0'.
  • # II.0'. Suppose we take H ⊆ G and contract a link A. The subgraph H becomes a subgraph K of G_A". How are w(G,H) and w(G_A",K) related?
  • # II.1'. Prove König's Theorem. Let G be a bipartite graph with bipartition (U, V). The largest size of a matching equals the smallest size of a vertex cover.
  • # II.2'. Assume G is connected and let T be a spanning tree. Prove that every circuit is the set sum (the symmetric difference) of fundamental circuits with respect to T. (For this problem and the following we consider a circuit as an edge set.)
  • # II.3'. Suppose you have a minimal set of circuits that generates all circuits by set summation. (a) Prove there are exactly p₁(G) circuits in your set. (b) How is that related to bases in vector spaces? This is not a proof question!
  • # II.4'. [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.5'. 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).
  • # II.6'. Prove this fundamental Theorem. A graph is bipartite if and only if it has no circuits of odd length.
  HW D, due W 3/9 or F 3/11: Hand in ## II.4, II.6, II.1', II.5'.


• Chapter III: 2-Connection.
  HW E, due M 3/21: Hand in ## III.1-3 and III.1'.
  • # III.1'. Prove the following "vertex" version of Theorem III.7. Theorem III.7'. Let G be an inseparable graph and let U, V be nonnull vertex sets in G. Then μ(G;U,V) ≥ 2 with some exceptions. Find the exceptional cases.
  • # III.2'. Assume G is connected. Prove that a vertex v is a cutpoint if and only if it has more than one bridge.


• Chapter IV: 3-Connection.
  HW F, due W 4/6 (strict due date; get to work well ahead of time): Hand in ## II.6', IV.2, IV.3(i), IV.4, and IV.3'.
  Also do # I.3' (for you to use, not to hand in).
  • # IV.1'. Prove that in an n-connected graph G, all vertex degrees are at least n.
  • # IV.2'. For Tutte n-connection, assume G has at least 4 edges. Is it necessary to assume G has at least 2n-1 edges?
  • # IV.3'. For verticial n-connection, assume G has at least 4 vertices. How can you fit complete graphs into this concept?
  HW G, due M 4/11 (strict due date): Hand in ## IV.5, IV.6, IV.7.


• Chapter VIII: Algebraic Duality.
  HW H, due M 4/25: Hand in ## VIII.1, 2, 1', 2'.
  HW I, due F 4/29 M 5/2: Hand in ## VIII.4, 4', 5'.
  • # VIII.1'. G is a connected graph and T is any spanning tree. Over a ring R, let H denote the incidence matrix of G and M the standard representation matrix of the chain-base B(G,T). [B(G,T) is Tutte's B(T); it is the chain-base associated to the cell-base T.] In both matrices, put the columns for T at the beginning. Show that M is the reduced echelon form of H.
    Correction. This should say: Show that M and H have the same row space. For that, the order of columns doesn't matter as long as it's the same in both matrices.
  • # VIII.2'. N means a chain-group from S = [6] to Z. (Thus a chain f is an element of Z^[6].) There are two problems, one for each chain-group:
    1. N is the chain group generated by all chains in which exactly four entries are nonzero.
    2. N' is the chain group generated by all chains in which exactly four entries are nonzero and the sum of the entries is 0.
    Each problem has two parts, (a) and (b). The parts are
    1. Find the elementary and primitive chains and the cell-bases.
    2. Find the dual chain group N* and its elementary and primitive chains and its cell-bases.
  • # VIII.3'. N being any primitive chain group on any set S, prove the following properties. (They are basic properties of a matroid.)
    1. Properties (i) and (ii) in Section VIII.11.
    2. Let Q_I be the class of subsets of S that do not contain the support of any primitive chain. Prove:
       1. The null set is in Q_I .
       2. If J is in Q_I and I is a subset of J, then I is in Q_I .
       3. If I and J are in Q_I and |I| < |J|, then there is x ∈ J − I such that I ∪ x is in Q_I .
    3. Let Q_B be the class of maximal members of Q_I . Prove:
       1. Q_B is nonempty.
       2. If A and B are in Q_B and x is in A, then there is y ∈ B such that [(A−x) ∪ y] ∈ Q_B .
    4. Prove that Q_B is the class of complements of cell-bases of N.
  • # VIII.4'. Let Ω be an orientation of the graph G and let N be the chain-group from the dart set E(Ω) to R that is generated by the rows of the incidence matrix M(Ω) defined in class (and in § VIII.10). Show that the cycle group Z₁(Ω; R) (which Tutte calls Γ(Ω, R)) is N*.
  • # VIII.5'. Let Ω be an orientation of the graph G. Show that the coboundary group B¹(Ω; R) (which Tutte calls Δ(Ω, R)) equals the chain-group N of the preceding problem.
  
  
• Chapter IX: Polynomials Associated with Graphs.
  HW J, due M 5/9 F 5/6: Hand in ## IX.3–4, IX.3' IX.1'–3'.
  HW K, due F 5/13: Hand in IX.1-2, IX.2' (corrected), 4'.
  Hint for IX.2: (Tutte meant Figs. III.2.1 and III.2.2.) Think of easier ways than slogging through the definition of Q_G.
  • # IX.1'. Find the chromatic polynomials of the graphs in Fig. III.2.2. Do not use the circuit formula in the book.
  • # IX.2'. Define the modified chromatic polynomial π_G(κ) by the formula (Corrected! (λ+1) was formerly (λ−1), which is wrong.)

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

    Here n := |V(G)| and 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.)
    1. Prove that π_G(κ) satisfies the deletion-contraction relation for every edge that is neither an isthmus nor a loop.
    2. Prove that π_G(κ) satisfies the multiplicative relation for a disjoint union of graphs.
    3. Deduce from (a-b) that all coefficients of π_G(κ) are nonnegative.
    4. Express the coefficients of the chromatic polynomial in terms of those of π_G(κ).
  • # IX.3'. Compute the chromatic polynomial of the graph H = K_n with the edges of a path of length 4 removed (n ≥ 5).
  • # IX.4'. This is for the graphs in IX.2.
    1. Find the Tutte polynomials (dichromates).
    2. Use the Tutte polynomial to find the flow polynomial of each graph.
    3. Find the flow number φ(G) of each graph.
    4. For each graph find a nowhere-zero cycle in Z_φ(G).

  ---

  To the main course page | syllabus and schedule page | dictionary page | meetings page | my home page.

  ---