# Determine the maximum collection of edge-disjoint xy-paths in Q n </msub> Let x

Determine the maximum collection of edge-disjoint xy-paths in ${Q}_{n}$
Let x be the vertex of all zeros and y be the vertex of all ones in the hypercube graph ${Q}_{n}$. We have to determine the maximum collection of edge-disjoint xy-paths in ${Q}_{n}$ and a minimum vertex cut of ${Q}_{n}$ separating x and y.
My work: We define a xy-path ${P}_{i}$ as follows:
Start from the vertex x and change the ${i}^{th}$ bit to 1 and then change all bits gradually one by one moving leftward from $i-1$ to 1 to n and back to i.
Note that all paths ${P}_{i}$ are edge-disjoint. Thus we have a maximum collection.
By Menger's Theorem, the second part follows.
You can still ask an expert for help

## Want to know more about Discrete math?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Alisa Jacobs
Step 1
The reasoning all the paths ${P}_{i}$ are edge-disjoint. Thus we have a maximum collection.
is nonsense. The empty set is a set of edge-disjoint paths. A set containing a single path is a set of edge-disjoint paths. There is nothing about being edge-disjoint that says your collection of paths is large in any way, let alone maximum.
You are not going to trick your way out of looking at cuts. If you think your collection of n edge-disjoint paths is maximum, find an edge cut of size n, and that will prove that you can't find a collection of $n+1$ paths (by the easy direction of Menger's theorem).
Yes, I said edge cut. Edge-disjoint paths go with edge cuts. If you want something that goes with a vertex cut, you should be looking for a collection of internally (vertex-)disjoint paths: paths that don't share any vertices other than the endpoints.
Step 2
That being said: yes, none of your paths ${P}_{1},{P}_{2},\dots ,{P}_{n}$ share any edges or (which is stronger) vertices other than x or y. That's because all internal vertices of path ${P}_{i}$ have the following property: the ${i}^{\text{th}}$ bit is 1, and the the $\left(i+1{\right)}^{\text{th}}$ bit is 0. No other path ${P}_{j}$ with $j\ne i$ contains a vertex with this property, because every other path will set the $\left(i+1{\right)}^{\text{th}}$ bit to 1 before setting the ${i}^{\text{th}}$ bit to 1.