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'.
  • # 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.
• HW B, due F 2/6: Hand in ## I.2' and I.3'.
  • # 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.


• Chapter II: Contractions and the Theorem of Menger.