Paper 4, Section II, G
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.
Typos? Please submit corrections to this page on GitHub.