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.