Paper 2, Section II, 17G

Graph Theory
Part II, 2020

(i) Define the local connectivity κ(a,b;G)\kappa(a, b ; G) for two non-adjacent vertices aa and bb in a graph GG. Prove Menger's theorem, that GG contains a set of κ(a,b;G)\kappa(a, b ; G) vertex-disjoint aba-b paths.

(ii) Recall that a subdivision TKrT K_{r} of KrK_{r} is any graph obtained from KrK_{r} by replacing its edges by vertex-disjoint paths. Let GG be a 3 -connected graph. Show that GG contains a TK3T K_{3}. Show further that GG contains a TK4T K_{4}. Must GG contain a TK5T K_{5}?