# A linkage problem

Hi there,

I wonder how I can use Sage to solve the following problem, without implementing a full-blown backtracking.

Let $G$ be an undirected simple graph with at least $2k$ vertices. The graph $G$ would need to be $2k-1$-vertex-connected for the problem to hope to have a solution, but this is perhaps beside the point. Let $X$ be a set of $2k$ distinct vertices $s_1,...,s_k,t_1,...,t_k$ of G. Pair these $2k$ vertices arbitrarily into k pairs $(s_i,t_i)$. The pair $(s_i,t_i)$ means that the vertex $s_i$ has been paired with the vertex $t_i$. This pairing doesn't altered the graph $G$ in any way. The problem consists of finding k pairwise vertex-disjoint paths between $s_i$ and $t_i$ for each i, or returns that it is not possible to do so.

A graph for which you can find the $k$ vertex-disjoint paths for any possible set $X$ is called *$k$-linked*.

Let me give you an example. Suppose I take the 3-cube graph. I am gonna see it as a graph of the polytope 3-cube because the image is better.

`P3=polytopes.hypercube(3)`

`Q3=P3.graph()`

`Q3.show()`

Let me choose 4 vertices arbitrary vertices for my set $X$, say $s_1=(1,1,1)$, $t_1=(-1,-1,1)$, $s_2=(1,-1,1)$ and $t_2=(-1,1,1)$. Pair the vertices as $(s_i,t_i)$. Then we cannot find 2 vertex-disjoint paths, one connecting $s_1$ to $t_1$ and another $s_2$ to $t_2$. However, if I choose $X$ to be $s_1=(1,1,1)$, $t_1=(-1,-1,1)$ and $s_2=(-1,-1,-1)$ and $t_2=(1,1,-1)$ we can.

As an aside this shows that the 3-CubeGraph is not *2-linked*.

Hope this is a bit clearer now.

Thank you in advance, and regards, Guillermo

Please give the code for an explicit graph $G$. Also, form the context it is hard to understand what is given, and what should be found. (The index $i$ is used for the "pairs". What are the edges of $G$? Are the $(s_i,t_i)$ for $i\in ?$

alledges of $G$. An example, with the expected solution to be found, possibly one among many, would be helpful.)To start with, consider in the sage interpreter

to see how to initialize a graph.

Hi Dan,

Thank you for your comment. I have explained the problem a bit more.

Regards, Guillermo