[Solved] CSDS455 Homework9

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 ab 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 v_xy such that for each u G distinct from x and y, uv_xy 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.