output = value or ['value', 'cutset']

Specify what the command returns: value is the connectivity value as a positive integer. cutset is a set of edges or vertices of size value that can be removed to disconnect the graph.

EdgeConnectivity returns the edge connectivity of a graph, that is the minimum number of edges whose removal disconnects the graph. The output option can be used to return a cut-set of minimal size. This set is typically not unique. The IsCutSet command can be used to test whether a set of edges is a cut-set.

VertexConnectivity returns the vertex connectivity of a graph, that is the minimum number of vertices whose removal disconnects the graph. The output option can be used to return a minimal set of vertices tha can be used to disconnnect the graph. Again, this set is not unique.

In the general case, both these commands call MaxFlow iteratively over pairs of vertices in the graph (or a related graph) and they call MinCut to compute the cut-set.

By an elementary theorem of graph theory, the vertex connectivity of a graph is less than or equal to the edge connectivity, which is less than or equal to the minimum degree.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$G≔\mathrm{Graph}\left(\left\{\left\{1\,2\right\}\,\left\{1\,3\right\}\,\left\{1\,4\right\}\,\left\{2\,3\right\}\,\left\{3\,4\right\}\,\left\{4\,5\right\}\,\left\{4\,6\right\}\,\left\{5\,6\right\}\right\}\right)$

$G≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 6\; vertices\; and\; 8\; edge(s)}$

$\mathrm{DrawGraph}\left(G\right)$

$\mathrm{MinimumDegree}\left(G\right)$

$2$

$\mathrm{EdgeConnectivity}\left(G\right)$

$2$

$\mathrm{VertexConnectivity}\left(G\,\mathrm{output}=\left['\mathrm{value}'\,'\mathrm{cutset}'\right]\right)$

$1,\left\{4\right\}$

$\mathrm{ArticulationPoints}\left(G\right)$

$\left[4\right]$

$P≔\mathrm{SpecialGraphs}:-\mathrm{PetersenGraph}\left(\right)$

$P≔\mathrm{Graph\; 2:\; an\; undirected\; graph\; with\; 10\; vertices\; and\; 15\; edge(s)}$

$\mathrm{DrawGraph}\left(P\right)$

$\mathrm{MinimumDegree}\left(P\right)$

$3$

$\mathrm{vc},\mathrm{vcut}≔\mathrm{VertexConnectivity}\left(P\,\mathrm{output}=\left['\mathrm{value}'\,'\mathrm{cutset}'\right]\right)$

$\mathrm{vc},\mathrm{vcut}≔3,\left\{2\,4\,7\right\}$

$\mathrm{DrawGraph}\left(\mathrm{DeleteVertex}\left(P\,\mathrm{vcut}\right)\right)$

$\mathrm{ec},\mathrm{ecut}≔\mathrm{EdgeConnectivity}\left(P\,\mathrm{output}=\left['\mathrm{value}'\,'\mathrm{cutset}'\right]\right)$

$\mathrm{ec},\mathrm{ecut}≔3,\left\{\left\{1\,2\right\}\,\left\{2\,3\right\}\,\left\{2\,9\right\}\right\}$

$\mathrm{IsCutSet}\left(P\,\mathrm{ecut}\right)$

$\mathrm{true}$

$\mathrm{DrawGraph}\left(\mathrm{DeleteEdge}\left(P\,\mathrm{ecut}\right)\right)$

$\mathrm{ec}=\mathrm{vc}$

$3=3$

The GraphTheory[EdgeConnectivity] and GraphTheory[VertexConnectivity] commands were updated in Maple 2024.

The output option was introduced in Maple 2024.

For more information on Maple 2024 changes, see Updates in Maple 2024.