Math 510
Introduction to Graph Theory
Spring 2026

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/4: Hand in ## I.1 – I.3 and I.1'.
• HW B, due F 2/6: Hand in ## I.2' and I.3'.
• Additional problems:
  • # I.1'. Prove that the following statements about a graph G are equivalent. Use anything in §§I.1-6.
    1. G is a tree (i.e., connected and every edge is an isthmus).
    2. G is connected and contains no circuits.
    3. G is connected and |E| = |V| − 1.
    4. In G, any two vertices are joined by exactly one arc, and G has no loops. (N.B. Usually this theorem is stated for simple graphs, thus I forgot about loops.)
  • # 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 statement by Tutte at the end of §I.6: We can characterize p₁(G) as the least number of edges whose deletion from G destroys every circuit.
  • # I.4'. Given G and a subgraph J, define an equivalence relation on E(G) \ E(J) by the transitive closure of A ∼ B if A and B are both incident to a vertex v not in J. Prove that the equivalence classes of ∼ are the edge sets of the nondegenerate bridges of J.
  • # I.5'. In a graph, what is the difference between a spanning forest and a maximal forest?
  • # I.6'. Let G be a graph with k components, each one isomorphic to K₂. How many spanning forests does G have? How many maximal forests does G have?


• Chapter II: Contractions and the Theorem of Menger.
• HW C, due F 2/13: Hand in ## I.4', II.2, II.1'.
• HW D, due F 2/20: Hand in ## I.5', II.4.
• HW E, due M 3/2: Hand in ## II.6, II.2', II.3', II.4'.
• Additional problems:
  • # II.1'. 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.2'. Prove this fundamental Theorem. A graph is bipartite if and only if it has no circuits of odd length.
  • # II.3'. 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.4'. 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? ((b) is not a proof question.)


• Chapter III: 2-Connection.
• HW F, due M 3/9: Hand in ## III.1-3 and III.1'.
• Additional problems:
  • # III.1'. Prove the following "vertex" version of Theorem III.7 and find the exceptions.
    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.
  • # III.2'. Assume G is connected. Prove that a vertex v is a cutpoint if and only if it has more than one bridge.
  • # III.3'. Prove, and specify the exceptions:
    Theorem III.A. Let G be an inseparable graph and let v ∈ V(G). Then G \ {v} is connected, with certain exceptions.


• Chapter IV: 3-Connection.
• HW G, due 3/20: Hand in ## I.6', III.3', IV.2, IV.3(i), (not IV.4), and IV.1'.
• HW H, due 3/27: Hand in ## IV.4, IV.6.
• Additional problems:
  • # IV.1' (corrected). Prove that in an n-connected graph G with |E(G)| > 2n, all vertex valencies are at least n. Conclude that the connectivity cannot be greater than the smallest valency (assuming enough edges).
  • # 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?


• Chapter VIII: Algebraic Duality.
• HW I, due 4/24: Hand in ## VIII.1, 2, 1'.
• HW J, due 5/1: Hand in ## VIII.3. Compare with deletion-contraction formulas for the spanning tree count and the chromatic, flow, and dichromatic polynomials.
• Additional problems:
  • # 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.]
    1. 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.
    2. In both matrices, put the columns for T at the beginning. Show that M is the reduced echelon form of H.
  • # 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 §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.