CSDS 455: Applied Graph Theory
Homework 9
Problem 1: Let a and b be distinct vertices of G. Prove that the minimum number of edges separating a
from b in G is equal to the maximum number of edge-disjoint a − b paths in G. (Hint: look at the line graph
of G.)
Problem 2: Let G be a k-connected graph for k ≥ 2. Prove that any k vertices lie on a common cycle of G.
Problem 3: Let G/xy be the simple graph created by contracting edge xy to create a new vertex vxy such
that for each u ∈ G distinct from x and y, uvxy is an edge of G/xy if and only if ux or uy is an edge of G.
(G/xy is the same as G · xy where we remove all loops and multiedges.)
Let G be a 3-connected graph. Prove that G/xy is 3-connected if and only if G − {x, y} is 2-connected.
