WOLFRAM

Wolfram Language & System Documentation Center

FindVertexIndependentPaths[g,s,t,k]

finds at most k vertex-independent paths from vertex s to vertex t in the graph g.

FindVertexIndependentPaths[{vw,…},…]

uses rules vw to specify the graph g.

Details
Details and Options Details and Options
Examples  
Basic Examples  
Scope  
Properties & Relations  
Possible Issues  
See Also
Related Guides
History
Cite this Page

FindVertexIndependentPaths

FindVertexIndependentPaths[g,s,t,k]

finds at most k vertex-independent paths from vertex s to vertex t in the graph g.

FindVertexIndependentPaths[{vw,…},…]

uses rules vw to specify the graph g.

Details

  • Vertex-independent paths are also known as independent paths or vertex disjoint paths.
  • FindVertexIndependentPaths returns a list of vertex-independent paths from s to t.
  • Each path is given as a list of vertices.
  • FindVertexIndependentPaths works with undirected graphs, directed graphs, multigraphs, and mixed graphs.

Examples

open all close all

Basic Examples  (1)

Find a vertex-independent path between two individual vertices in a graph:

Wolfram Language code: g = GraphData["ButterflyGraph"]
Wolfram Language code: FindVertexIndependentPaths[g, 3, 4, 2]

Show the path:

Wolfram Language code: HighlightGraph[g, PathGraph[First[%]]]

Scope  (6)

FindVertexIndependentPaths works with undirected graphs:

Wolfram Language code: FindVertexIndependentPaths[[image], 1, 6, 2]

Directed graphs:

Wolfram Language code: FindVertexIndependentPaths[[image], 1, 6, 2]

Multigraphs:

Wolfram Language code: FindVertexIndependentPaths[[image], 1, 6, 2]

Mixed graphs:

Wolfram Language code: FindVertexIndependentPaths[[image], 1, 6, 2]

Use rules to specify the graph:

Wolfram Language code: FindVertexIndependentPaths[{1 -> 2, 1 -> 5, 2 -> 3, 3 -> 4, 4 -> 5, 6 -> 3, 4 -> 6}, 1, 6, 2]

FindVertexIndependentPaths works with large graphs:

Wolfram Language code: g = GridGraph[{10, 10, 10, 10}];
Wolfram Language code: FindVertexIndependentPaths[g, 3, 10, 2]//Timing

Properties & Relations  (2)

FindVertexIndependentPaths only returns simple paths:

Wolfram Language code: FindVertexIndependentPaths[[image], 1, 3, 3]

VertexConnectivity gives the maximum number of vertex-independent paths:

Wolfram Language code: g = ExampleData[{"NetworkGraph", "ZacharyKarateClub"}];
Wolfram Language code: FindVertexIndependentPaths[g, 1, 32, Infinity]//Length
Wolfram Language code: VertexConnectivity[g, 1, 32]

Possible Issues  (1)

Find a largest set of vertex-independent paths between two vertices:

Wolfram Language code: g = GridGraph[{2, 3}];
Wolfram Language code: FindVertexIndependentPaths[g, 2, 5, Infinity]
Wolfram Language code: HighlightGraph[g, PathGraph[#]]& /@ %

Another vertex-independent path:

Wolfram Language code: HighlightGraph[g, PathGraph[{2, 4, 3, 5}]]
Wolfram Research (2014), FindVertexIndependentPaths, Wolfram Language function, https://reference.wolfram.com/language/ref/FindVertexIndependentPaths.html (updated 2015).

Text

Wolfram Research (2014), FindVertexIndependentPaths, Wolfram Language function, https://reference.wolfram.com/language/ref/FindVertexIndependentPaths.html (updated 2015).

CMS

Wolfram Language. 2014. "FindVertexIndependentPaths." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindVertexIndependentPaths.html.

APA

Wolfram Language. (2014). FindVertexIndependentPaths. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindVertexIndependentPaths.html

BibTeX

@misc{reference.wolfram_2026_findvertexindependentpaths, author="Wolfram Research", title="{FindVertexIndependentPaths}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindVertexIndependentPaths.html}", note=[Accessed: 12-June-2026]}

BibLaTeX

@online{reference.wolfram_2026_findvertexindependentpaths, organization={Wolfram Research}, title={FindVertexIndependentPaths}, year={2015}, url={https://reference.wolfram.com/language/ref/FindVertexIndependentPaths.html}, note=[Accessed: 12-June-2026]}