Paper 4, Section II, G

Graph Theory
Part II, 2016

State Menger's theorem in both the vertex form and the edge form. Explain briefly how the edge form of Menger's theorem may be deduced from the vertex form.

(a) Show that if GG is 3 -connected then GG contains a cycle of even length.

(b) Let GG be a connected graph with all degrees even. Prove that λ(G)\lambda(G) is even. [Hint: if SS is a minimal set of edges whose removal disconnects GG, let HH be a component of GSG-S and consider the degrees of the vertices of HH in the graph GSG-S.] Give an example to show that κ(G)\kappa(G) can be odd.