Let G be a 2-connected nonbipartite graph on 2n vertices. Show that the vertex set of G can be split into two classes of n elements such that the edges joining the two classes form a connected, spanning subgraph.
L. Lovasz combinatorics proposedcombinatoricsgraph theory