Paper 4, Section II, G
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 is 3 -connected then contains a cycle of even length.
(b) Let be a connected graph with all degrees even. Prove that is even. [Hint: if is a minimal set of edges whose removal disconnects , let be a component of and consider the degrees of the vertices of in the graph .] Give an example to show that can be odd.