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.
Reviews
There are no reviews yet.