1 | initial version |

You may use the dancing links solver in Sage to do this:

```
sage: G = graphs.CompleteGraph(6)
sage: G.vertices()
[0, 1, 2, 3, 4, 5]
sage: rows = [[a,b] for (a,b,label) in G.edges()]
sage: dlx = dlx_solver(rows)
sage: indices = dlx.one_solution()
sage: indices
[2, 5, 14]
sage: [rows[i] for i in indices]
[[0, 3], [1, 2], [4, 5]]
```

or just use matching:

```
sage: G.matching()
[(0, 5, None), (1, 4, None), (2, 3, None)]
```

... if I understand your question correctly.

2 | No.2 Revision |

You may use the dancing links solver in Sage to do this:

```
sage: G = graphs.CompleteGraph(6)
sage: G.vertices()
[0, 1, 2, 3, 4, 5]
sage: rows = [[a,b] for (a,b,label) in G.edges()]
sage: dlx = dlx_solver(rows)
sage: indices = dlx.one_solution()
sage: indices
[2, 5, 14]
sage: [rows[i] for i in indices]
[[0, 3], [1, 2], [4, 5]]
```

or just ~~use ~~search for a matching:

```
sage: G.matching()
[(0, 5, None), (1, 4, None), (2, 3, None)]
```

... if I understand your question correctly.

3 | No.3 Revision |

You may use the dancing links solver in Sage to do this:

```
sage: G = graphs.CompleteGraph(6)
sage: G.vertices()
[0, 1, 2, 3, 4, 5]
sage: rows = [[a,b] for (a,b,label) in G.edges()]
sage: dlx = dlx_solver(rows)
sage: indices = dlx.one_solution()
sage: indices
[2, 5, 14]
sage: [rows[i] for i in indices]
[[0, 3], [1, 2], [4, 5]]
```

or just search for a matching:

```
sage: G.matching()
[(0, 5, None), (1, 4, None), (2, 3, None)]
```

... if I understand your question correctly.

**EDIT:**

Okay, I see now that you updated the question. I think you want to use the method `disjoint_routed_paths`

:

```
sage: G = polytopes.hypercube(3).graph()
sage: edges = [(tuple(u.vector()), tuple(v.vector())) for (u,v,label) in G.edges()]
sage: G = Graph(edges, format='list_of_edges')
sage: s1=(1,1,1); t1=(-1,-1,1); s2=(1,-1,1); t2=(-1,1,1)
sage: pairs = [(s1,t1), (s2,t2)]
sage: G.disjoint_routed_paths(pairs)
Traceback (most recent call last):
...
EmptySetError: The disjoint routed paths do not exist.
```

and here it works:

```
sage: pairs = [((1,1,1), (-1,-1,1)), ((-1,-1,-1), (1,1,-1))]
sage: paths = G.disjoint_routed_paths(pairs)
sage: paths
[Subgraph of (): Graph on 3 vertices, Subgraph of (): Graph on 3 vertices]
sage: paths[0].edges()
[((-1, -1, 1), (1, -1, 1), 1), ((1, -1, 1), (1, 1, 1), 1)]
sage: paths[1].edges()
[((-1, -1, -1), (-1, 1, -1), 1), ((-1, 1, -1), (1, 1, -1), 1)]
```

So you want to write a function like this maybe :

```
sage: def is_k_linked(G, k):
....: V = G.vertices()
....: for S in Subsets(range(len(V)), 2*k):
....: for R in Subsets(S, k):
....: L = S.difference(R)
....: pairs = [(V[a],V[b]) for (a,b) in zip(L,R)]
....: try:
....: G.disjoint_routed_paths(pairs)
....: except EmptySetError:
....: return False
....: return True
....:
sage: is_k_linked(G,2) # something is wrong in my code, as it should return False
True
```

I do not have time now to debug this further now.

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.