Let x be the vertex of all zeros and y be the vertex of all ones in the hypercube graph . We have to determine the maximum collection of edge-disjoint xy-paths in and a minimum vertex cut of separating x and y.
My work: We define a xy-path as follows:
Start from the vertex x and change the bit to 1 and then change all bits gradually one by one moving leftward from to 1 to n and back to i.
Note that all paths are edge-disjoint. Thus we have a maximum collection.
By Menger's Theorem, the second part follows.