WOLFRAM

Wolfram Language & System Documentation Center

FindEdgeCut[g]

finds a smallest edge cut of the graph g.

FindEdgeCut[g,s,t]

finds a smallest s-t edge cut of the graph g.

FindEdgeCut[{vw,…},…]

uses rules vw to specify the graph g.

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

FindEdgeCut

FindEdgeCut[g]

finds a smallest edge cut of the graph g.

FindEdgeCut[g,s,t]

finds a smallest s-t edge cut of the graph g.

FindEdgeCut[{vw,…},…]

uses rules vw to specify the graph g.

Details and Options

  • An edge cut of a graph g is a set of edges whose deletion from g disconnects g.
  • The s-t edge cut is a list of edges who deletion from g disconnects g with s and t in two different connected components.
  • For weighted graphs, FindEdgeCut gives an edge cut with the smallest sum of edge weights.
  • For a disconnected graph, FindEdgeCut will return an empty list {}.
  • The following option can be given:
  • EdgeWeight Automaticedge weight for each edge

Examples

open all close all

Basic Examples  (2)

Find a smallest edge cut:

Wolfram Language code: g = [image];
Wolfram Language code: FindEdgeCut[g]

Highlight an edge cut:

Wolfram Language code: HighlightGraph[g, %]

Find a smallest edge cut between two vertices:

Wolfram Language code: FindEdgeCut[[image], 2, 5]

Scope  (8)

FindEdgeCut works with undirected graphs:

Wolfram Language code: FindEdgeCut[[image]]

Directed graphs:

Wolfram Language code: FindEdgeCut[[image]]

Weighted graphs:

Wolfram Language code: FindEdgeCut[[image]]

Multigraphs:

Wolfram Language code: FindEdgeCut[[image]]

Mixed graphs:

Wolfram Language code: FindEdgeCut[[image]]

Find an s-t edge cut:

Wolfram Language code: FindEdgeCut[[image], 1, 4]

Use rules to specify the graph:

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

FindEdgeCut works with large graphs:

Wolfram Language code: g = GridGraph[{10, 10, 10, 10}];
Wolfram Language code: FindEdgeCut[g]//Length//Timing

Options  (1)

EdgeWeight  (1)

By default, the edge weight of an edge is taken to be its EdgeWeight property if available, otherwise 1:

Wolfram Language code: FindEdgeCut[[image]]

Use EdgeWeight->weights to set the edge weight:

Wolfram Language code: FindEdgeCut[[image], EdgeWeight -> Range[5]]

Applications  (1)

Find the smallest set of relations disconnecting two members in a friendship network of a karate club:

Wolfram Language code: g = ExampleData[{"NetworkGraph", "ZacharyKarateClub"}];
Wolfram Language code: Part[VertexList[g], Ordering[KatzCentrality[g, 0.1], -2]]
Wolfram Language code: ecut = FindEdgeCut[g, 1, 34]

Highlight the result:

Wolfram Language code: HighlightGraph[g, Join[{1, 34}, ecut], GraphHighlightStyle -> "Thick"]

Properties & Relations  (4)

Use EdgeConnectivity to obtain the size of the edge cut:

Wolfram Language code: g = [image];
Wolfram Language code: FindEdgeCut[g]
Wolfram Language code: EdgeConnectivity[g]

Use FindMinimumCut to obtain a partition of vertices associated to the edge cut:

Wolfram Language code: g = [image];
Wolfram Language code: FindEdgeCut[g]
Wolfram Language code: Last[FindMinimumCut[g]]

Deleting the edge cut disconnects the graph:

Wolfram Language code: g = [image];
Wolfram Language code: FindEdgeCut[g]
Wolfram Language code: ConnectedGraphQ[EdgeDelete[g, %]]

FindEdgeCut returns an empty list for a disconnected graph:

Wolfram Language code: g = [image];
Wolfram Language code: FindEdgeCut[g]
Wolfram Language code: ConnectedGraphQ[g]
Wolfram Research (2012), FindEdgeCut, Wolfram Language function, https://reference.wolfram.com/language/ref/FindEdgeCut.html (updated 2015).

Text

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

CMS

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

APA

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

BibTeX

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

BibLaTeX

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