---
title: "Connectedness"
canonical: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Multigraphs/multig-connectedness.html"
source: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Multigraphs/multig-connectedness.md"
part: "Combinatorics"
chapter: "Multigraphs"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Combinatorics", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/index-combinatorics.md"}
  - {"title": "Multigraphs", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Multigraphs/index-multigraphs.md"}
prev: {"title": "Adjacency and Degree", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Multigraphs/multig-adj-deg.md"}
next: {"title": "Spanning Trees", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Multigraphs/spanning-tree.md"}
intrinsics:
  - {"name": "IsConnected", "signature": "IsConnected(G): GrphMultUnd -> BoolElt"}
  - {"name": "Components", "signature": "Components(G): GrphMultUnd -> [ { GrphVert } ]"}
  - {"name": "Component", "signature": "Component(u): GrphVert -> GrphMult"}
  - {"name": "IsSeparable", "signature": "IsSeparable(G): GrphMultUnd -> BoolElt"}
  - {"name": "IsBiconnected", "signature": "IsBiconnected(G): GrphMultUnd -> BoolElt"}
  - {"name": "CutVertices", "signature": "CutVertices(G): GrphMultUnd -> { GrphVert}"}
  - {"name": "Bicomponents", "signature": "Bicomponents(G): GrphMultUnd -> [ { GrphVert } ]"}
  - {"name": "IsStronglyConnected", "signature": "IsStronglyConnected(G): GrphMultDir -> BoolElt"}
  - {"name": "IsWeaklyConnected", "signature": "IsWeaklyConnected(G): GrphMultDir -> BoolElt"}
  - {"name": "StronglyConnectedComponents", "signature": "StronglyConnectedComponents(G): GrphMultDir -> [ { GrphVert} ]"}
  - {"name": "Component", "signature": "Component(u): GrphVert -> GrphMult"}
  - {"name": "IsTriconnected", "signature": "IsTriconnected(G): GrphMultUnd -> BoolElt"}
  - {"name": "Splitcomponents", "signature": "Splitcomponents(G): GrphMultUnd -> [ { GrphVert} ], [ [ GrphVert ]]"}
  - {"name": "SeparationVertices", "signature": "SeparationVertices(G): GrphMultUnd -> [ [ GrphVert ]], [ { GrphVert} ]"}
  - {"name": "MaximumMatching", "signature": "MaximumMatching(G : parameters): GrphMultUnd -> [ { GrphEdge rbrace ]"}
  - {"name": "VertexSeparator", "signature": "VertexSeparator(G : parameters): GrphMult -> [ GrphVert ]"}
  - {"name": "VertexConnectivity", "signature": "VertexConnectivity(G : parameters): GrphMult -> RngIntElt, [ GrphVert ]"}
  - {"name": "IsKVertexConnected", "signature": "IsKVertexConnected(G, k : parameters): GrphMult, RngIntElt -> BoolElt"}
  - {"name": "EdgeSeparator", "signature": "EdgeSeparator(G : parameters): GrphMult -> [ GrphEdge ]"}
  - {"name": "EdgeConnectivity", "signature": "EdgeConnectivity(G : parameters): GrphMult -> RngIntElt, [ GrphEdge ]"}
  - {"name": "IsKEdgeConnected", "signature": "IsKEdgeConnected(G, k : parameters): GrphMult, RngIntElt -> BoolElt"}
examples:
  - "ex-e96180"
---

<a id="multig-connectedness"></a>
<a id="multigraph-sec-connect-graph"></a>
# Connectedness

All the functions relating to connectivity issues are the same for simple graphs and multigraphs. See Section [Connectedness in a Graph](https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/connectedness-path-circuit.md#graph-subsec-connect-graph) and its subsections for specific details about the algorithms underlying these functions.

<a id="multig-connectedness-graph"></a>
<a id="multigraph-subsec-connect-graph"></a>
## Connectedness in a Multigraph

<a id="function-isconnected-grphmultund"></a>
### `IsConnected(G): GrphMultUnd -> BoolElt`

Returns `true` if and only if the undirected graph $G$ is a connected graph.

<a id="function-components-grphmultund"></a>
### `Components(G): GrphMultUnd -> [ { GrphVert } ]`

The connected components of the undirected graph $G$. These are returned in the form of a sequence of subsets of the vertex-set of $G$.

<a id="function-component-grphvert"></a>
### `Component(u): GrphVert -> GrphMult`

The subgraph corresponding to the connected component of the multigraph $G$ containing vertex $u$. The support and vertex/edge decorations are *not* retained in the resulting (structural) subgraph.

<a id="function-isseparable-grphmultund"></a>
### `IsSeparable(G): GrphMultUnd -> BoolElt`

Returns `true` if and only if the graph $G$ is connected and has at least one cut vertex.

<a id="function-isbiconnected-grphmultund"></a>
### `IsBiconnected(G): GrphMultUnd -> BoolElt`

Returns `true` if and only if the graph $G$ is biconnected. The graph $G$ must be undirected.

<a id="function-cutvertices-grphmultund"></a>
### `CutVertices(G): GrphMultUnd -> { GrphVert}`

The set of cut vertices for the connected undirected graph $G$ (as a set of vertices).

<a id="function-bicomponents-grphmultund"></a>
### `Bicomponents(G): GrphMultUnd -> [ { GrphVert } ]`

The biconnected components of the undirected graph $G$. These are returned in the form of a sequence of subsets of the vertex-set of $G$. The graph may be disconnected.

<a id="multig-digraph"></a>
<a id="multigraph-subsec-connect-digraph"></a>
## Connectedness in a Multidigraph

<a id="function-isstronglyconnected-grphmultdir"></a>
### `IsStronglyConnected(G): GrphMultDir -> BoolElt`

Returns `true` if and only if the multidigraph $G$ is strongly connected.

<a id="function-isweaklyconnected-grphmultdir"></a>
### `IsWeaklyConnected(G): GrphMultDir -> BoolElt`

Returns `true` if and only if the multidigraph $G$ is weakly connected.

<a id="function-stronglyconnectedcomponents-grphmultdir"></a>
### `StronglyConnectedComponents(G): GrphMultDir -> [ { GrphVert} ]`

The strongly connected components of the multidigraph $G$. These are returned in the form of a sequence of subsets of the vertex-set of $G$.

<a id="function-component-grphvert-2"></a>
### `Component(u): GrphVert -> GrphMult`

The subgraph corresponding to the connected component of the multidigraph $G$ containing vertex $u$. The support and vertex/edge decorations are *not* retained in the resulting (structural) subgraph.

<a id="multig-triconnectivity"></a>
<a id="multigraph-subsec-triconn"></a>
## Triconnectivity for Multigraphs

We refer the reader to Subsection [Graph Triconnectivity](https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/connectedness-path-circuit.md#graph-subsec-triconn) of the graphs chapter for details about the triconnectivity algorithm implemented here, and especially about the meaning of the `Splitcomponents` function. The triconnectivity algorithm applies to undirected graphs only.

<a id="function-istriconnected-grphmultund"></a>
### `IsTriconnected(G): GrphMultUnd -> BoolElt`

Returns `true` if and only if $G$ is triconnected. The graph $G$ must be undirected.

<a id="function-splitcomponents-grphmultund"></a>
### `Splitcomponents(G): GrphMultUnd -> [ { GrphVert} ], [ [ GrphVert ]]`

The split components of the undirected graph $G$. These are returned in the form of a sequence of subsets of the vertex-set of $G$. The graph may be disconnected. The second return value returns the cut vertices and the separation pairs as sequences of one or two vertices respectively.

<a id="function-separationvertices-grphmultund"></a>
### `SeparationVertices(G): GrphMultUnd -> [ [ GrphVert ]], [ { GrphVert} ]`

The cut vertices and/or the separation pairs of the undirected graph $G$ as a sequence of sequences of one and/or two vertices respectively. The graph may be disconnected. The second return value returns the split components of $G$ .

<a id="multig-maxmatching"></a>
<a id="multigraph-subsec-maxmatching"></a>
## Maximum Matching in Bipartite Multigraphs

We refer the reader to Subsection [Maximum Matching in Bipartite Graphs](https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/connectedness-path-circuit.md#graph-subsec-maxmatching) for information about the maximum matching algorithm.

<a id="function-maximummatching-grphmultund"></a>
### `MaximumMatching(G : parameters): GrphMultUnd -> [ { GrphEdge rbrace ]`

```magma
Al: MonStg                    Default: "PushRelabel"
```

A maximum matching in the bipartite graph $G$. The matching is returned as a sequence of edges of G. The parameter `Al` enables the user to select the algorithm which is to be used: `Al := "PushRelabel"` or `Al := "Dinic"`.

<a id="multig-gen-connectivity"></a>
<a id="multigraph-subsec-gen-connect"></a>
## General Vertex and Edge Connectivity in Multigraphs and Multidigraphs

See Subsection [General Vertex and Edge Connectivity in Graphs and Digraphs](https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/connectedness-path-circuit.md#graph-subsec-gen-connect) for details about the algorithms underlying the functions listed below. These functions apply to both undirected and directed graphs.

<a id="function-vertexseparator-grphmult"></a>
### `VertexSeparator(G : parameters): GrphMult -> [ GrphVert ]`

```magma
Al: MonStg                    Default: "PushRelabel"
```

If $G$ is an undirected graph, a *vertex separator* for $G$ is a smallest set of vertices $S$ such that for any $u$, $v\in V(G)$, every path connecting $u$ and $v$ passes through at least one vertex of $S$.

If $G$ is a directed graph, a vertex separator for $G$ is a smallest set of vertices $S$ such that for any $u$, $v\in V(G)$, every directed path from $u$ to $v$ passes through at least one vertex of $S$.

`VertexSeparator` returns the vertex separator of $G$ as a sequence of vertices of $G$. The parameter `Al` enables the user to select the algorithm which is to be used: `Al := "PushRelabel"` or `Al := "Dinic"`.

<a id="function-vertexconnectivity-grphmult"></a>
### `VertexConnectivity(G : parameters): GrphMult -> RngIntElt, [ GrphVert ]`

```magma
Al: MonStg                    Default: "PushRelabel"
```

Returns the vertex connectivity of the graph $G$, the size of a minimum vertex separator of $G$. Also returns a vertex separator for $G$ as the second value. The parameter `Al` enables the user to select the algorithm which is to be used: `Al := "PushRelabel"` or `Al := "Dinic"`.

<a id="function-iskvertexconnected-grphmult-rngintelt"></a>
### `IsKVertexConnected(G, k : parameters): GrphMult, RngIntElt -> BoolElt`

```magma
Al: MonStg                    Default: "PushRelabel"
```

Returns `true` if the vertex connectivity of the graph $G$ is at least $k$, `false` otherwise. The parameter `Al` enables the user to select the algorithm which is to be used: `Al := "PushRelabel"` or `Al := "Dinic"`.

<a id="function-edgeseparator-grphmult"></a>
### `EdgeSeparator(G : parameters): GrphMult -> [ GrphEdge ]`

```magma
Al: MonStg                    Default: "PushRelabel"
```

If $G$ is an undirected graph, an *edge separator* for $G$ is a smallest set of edges $T$ such that for any $u$, $v\in V(G)$, every path connecting $u$ and $v$ passes through at least one edge of $T$.

If $G$ is a directed graph, an edge separator for $G$ is a smallest set of edges $T$ such that for any $u$, $v\in V(G)$, every directed path from $u$ to $v$ passes through at least one edge of $T$.

`EdgeSeparator` returns the edge separator of $G$ as a sequence of edges of $G$. The parameter `Al` enables the user to select the algorithm which is to be used: `Al := "PushRelabel"` or `Al := "Dinic"`.

<a id="function-edgeconnectivity-grphmult"></a>
### `EdgeConnectivity(G : parameters): GrphMult -> RngIntElt, [ GrphEdge ]`

```magma
Al: MonStg                    Default: "PushRelabel"
```

Returns the edge connectivity of the graph $G$, the size of a minimum edge separator of $G$. Also returns as the second value an edge separator for $G$. The parameter `Al` enables the user to select the algorithm which is to be used: `Al := "PushRelabel"` or `Al := "Dinic"`.

<a id="function-iskedgeconnected-grphmult-rngintelt"></a>
### `IsKEdgeConnected(G, k : parameters): GrphMult, RngIntElt -> BoolElt`

```magma
Al: MonStg                    Default: "PushRelabel"
```

Returns `true` if the edge connectivity of the graph $G$ is at least $k$, `false` otherwise. The parameter `Al` enables the user to select the algorithm which is to be used: `Al := "PushRelabel"` or `Al := "Dinic"`.

<a id="example-ex-e96180"></a>
### `Example: Connectivity of a Multigraph (ex-e96180)`

We demonstrate that the connectivity functions deal properly with multiple edges.

```magma
> G := MultiGraph< 3 | < 1, {2, 3} >, < 1, {2, 3} >, < 2, {2, 3} > >;
> G;
Multigraph
Vertex  Neighbours

1       3 2 3 2 ;
2       3 2 2 1 1 ;
3       2 1 1 ;

> EdgeConnectivity(G);
3
> EdgeSeparator(G);
[ < {3, 2}, 11 >, < {1, 2}, 5 >, < {1, 2}, 1 > ]
```
