# Question:Finding pairwise vertex disjoint paths between two vertices with maximum size.

## Question:Finding pairwise vertex disjoint paths between two vertices with maximum size.

Maple 2023

Vertex disjoint paths are paths that only share their first and last vertices.  In Maple, we can compute the maximum number of pairwise vertex disjoint paths from x to y by the function `MaxFlow`.

For example:

```with(GraphTheory):
with(SpecialGraphs):
g:=IcosahedronGraph():
HighlightVertex(g, {1,7},"DodgerBlue"):
DrawGraph(g);
g1:=MakeWeighted(g);
mxf:=MaxFlow(g1,1,7)
```

5

Matrix(12, 12, [[0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0], [0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0], [0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1], [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0]])

So  we know that the maximum number  of vertex-disjoint paths between vertices "1" and "7" is 5.

But can we obtain more information from `MaxFlow`, such as finding  five (i.e., the maximum number) vertex-disjoint paths between vertices "1" and "7" ? (These five paths may not be unique.)

Here is a set of five vertex-disjoint paths connecting vertices "1" and "7" that I observed manually, each marked with a different color.

﻿