---
title: "Adjacency and Degree"
canonical: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/adjacency-degree.html"
source: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/adjacency-degree.md"
part: "Combinatorics"
chapter: "Graphs"
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": "Graphs", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/index-graphs.md"}
prev: {"title": "Elementary Graph Predicates", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/Boolean.md"}
next: {"title": "Connectedness", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/connectedness-path-circuit.md"}
intrinsics:
  - {"name": "Degree", "signature": "Degree(u): GrphVert -> RngIntElt"}
  - {"name": "Alldeg", "signature": "Alldeg(G, n): GrphUnd, RngIntElt -> { GrphVert}"}
  - {"name": "MaximumDegree", "signature": "MaximumDegree(G): GrphUnd -> RngIntElt, GrphVert"}
  - {"name": "Maxdeg", "signature": "Maxdeg(G): GrphUnd -> RngIntElt, GrphVert"}
  - {"name": "MinimumDegree", "signature": "MinimumDegree(G): GrphUnd -> RngIntElt, GrphVert"}
  - {"name": "Mindeg", "signature": "Mindeg(G): GrphUnd -> RngIntElt, GrphVert"}
  - {"name": "DegreeSequence", "signature": "DegreeSequence(G): Grph -> [ { GrphVert} ]"}
  - {"name": "Valence", "signature": "Valence(G): GrphUnd -> RngIntElt"}
  - {"name": "Neighbours", "signature": "Neighbours(u): GrphVert -> { GrphVert}"}
  - {"name": "Neighbors", "signature": "Neighbors(u): GrphVert -> { GrphVert}"}
  - {"name": "IncidentEdges", "signature": "IncidentEdges(u): GrphVert -> { GrphEdge}"}
  - {"name": "Bipartition", "signature": "Bipartition(G): GrphUnd -> [ { GrphVert} ]"}
  - {"name": "MinimumDominatingSet", "signature": "MinimumDominatingSet(G): GrphUnd -> SetEnum"}
  - {"name": "InDegree", "signature": "InDegree(u): GrphVert -> RngIntElt"}
  - {"name": "OutDegree", "signature": "OutDegree(u): GrphVert -> RngIntElt"}
  - {"name": "Degree", "signature": "Degree(u): GrphVert -> RngIntElt"}
  - {"name": "Alldeg", "signature": "Alldeg(G, n): GrphDir, RngIntElt -> { GrphVert}"}
  - {"name": "MaximumInDegree", "signature": "MaximumInDegree(G): GrphDir -> RngIntElt, GrphVert"}
  - {"name": "Maxindeg", "signature": "Maxindeg(G): GrphDir -> RngIntElt, GrphVert"}
  - {"name": "MaximumOutDegree", "signature": "MaximumOutDegree(G): GrphDir -> RngIntElt, GrphVert"}
  - {"name": "Maxoutdeg", "signature": "Maxoutdeg(G): GrphDir -> RngIntElt, GrphVert"}
  - {"name": "MinimumInDegree", "signature": "MinimumInDegree(G): GrphDir -> RngIntElt, GrphVert"}
  - {"name": "Minindeg", "signature": "Minindeg(G): GrphDir -> RngIntElt, GrphVert"}
  - {"name": "MinimumOutDegree", "signature": "MinimumOutDegree(G): GrphDir -> RngIntElt, GrphVert"}
  - {"name": "Minoutdeg", "signature": "Minoutdeg(G): GrphDir -> RngIntElt, GrphVert"}
  - {"name": "MaximumDegree", "signature": "MaximumDegree(G): GrphDir -> RngIntElt, GrphVert"}
  - {"name": "Maxdeg", "signature": "Maxdeg(G): GrphDir -> RngIntElt, GrphVert"}
  - {"name": "MinimumDegree", "signature": "MinimumDegree(G): GrphDir -> RngIntElt, GrphVert"}
  - {"name": "Mindeg", "signature": "Mindeg(G): GrphDir -> RngIntElt, GrphVert"}
  - {"name": "DegreeSequence", "signature": "DegreeSequence(G): Grph -> [ { GrphVert} ]"}
  - {"name": "InNeighbours", "signature": "InNeighbours(u): GrphVert -> { GrphVert}"}
  - {"name": "InNeighbors", "signature": "InNeighbors(u): GrphVert -> { GrphVert}"}
  - {"name": "OutNeighbours", "signature": "OutNeighbours(u): GrphVert -> { GrphVert}"}
  - {"name": "OutNeighbors", "signature": "OutNeighbors(u): GrphVert -> { GrphVert}"}
  - {"name": "IncidentEdges", "signature": "IncidentEdges(u): GrphVert -> { GrphEdge}"}
---

<a id="adjacency-degree"></a>
<a id="graph-sec-adj"></a>
# Adjacency and Degree

## Adjacency and Degree Functions for a Graph

<a id="function-degree-grphvert"></a>
### `Degree(u): GrphVert -> RngIntElt`

Given a vertex $u$ of the graph $G$, return the degree of $u$, ie the number of edges incident to $u$.

<a id="function-alldeg-grphund-rngintelt"></a>
### `Alldeg(G, n): GrphUnd, RngIntElt -> { GrphVert}`

Given a graph $G$, and a non-negative integer $n$, return the set of all vertices of $G$ that have degree equal to $n$.

<a id="function-maximumdegree-grphund"></a>
### `MaximumDegree(G): GrphUnd -> RngIntElt, GrphVert`

<a id="function-maxdeg-grphund"></a>
### `Maxdeg(G): GrphUnd -> RngIntElt, GrphVert`

The maximum of the degrees of the vertices of the graph $G$. This function returns two values: the maximum degree, and a vertex of $G$ having that degree.

<a id="function-minimumdegree-grphund"></a>
### `MinimumDegree(G): GrphUnd -> RngIntElt, GrphVert`

<a id="function-mindeg-grphund"></a>
### `Mindeg(G): GrphUnd -> RngIntElt, GrphVert`

The minimum of the degrees of the vertices of the graph $G$. This function returns two values: the minimum degree, and a vertex of $G$ having that degree.

<a id="function-degreesequence-grph"></a>
### `DegreeSequence(G): Grph -> [ { GrphVert} ]`

Given a graph $G$ such that the maximum degree of any vertex of $G$ is $r$, return a sequence $D$ of length $r+1$, such that $D[i]$, $1 \leq i \leq r+1$, is the number of vertices in $G$ having degree $i-1$.

<a id="function-valence-grphund"></a>
### `Valence(G): GrphUnd -> RngIntElt`

Given a regular graph $G$, return the valence of $G$ (the degree of any vertex).

<a id="function-neighbours-grphvert"></a>
### `Neighbours(u): GrphVert -> { GrphVert}`

<a id="function-neighbors-grphvert"></a>
### `Neighbors(u): GrphVert -> { GrphVert}`

Given a vertex $u$ of the graph $G$, return the set of vertices of $G$ that are adjacent to $u$.

<a id="function-incidentedges-grphvert-2"></a>
### `IncidentEdges(u): GrphVert -> { GrphEdge}`

The set of all edges incident with the vertex $u$.

<a id="function-bipartition-grphund"></a>
### `Bipartition(G): GrphUnd -> [ { GrphVert} ]`

Given a bipartite graph $G$, return its two partite sets in the form of a pair of subsets of $V(G)$.

<a id="function-minimumdominatingset-grphund"></a>
### `MinimumDominatingSet(G): GrphUnd -> SetEnum`

A dominating set $S$ of a graph $G$ is such that the vertices of $S$ together with the vertices adjacent to vertices in $S$ form the vertex-set of $G$. A dominating set $S$ is minimal if no proper subset of $S$ is a dominating set. A minimum dominating set is a minimal dominating set of smallest size. The algorithm implemented is a backtrack algorithm (see [[Chr75](https://docs.magma-maths.org/v2.30-1/references.md#cite-christo75)] p. 41).

<a id="digraph"></a>
<a id="graph-subsec-digraph-adj-deg"></a>
## Adjacency and Degree Functions for a Digraph

<a id="function-indegree-grphvert"></a>
### `InDegree(u): GrphVert -> RngIntElt`

The number of edges directed into the vertex $u$ belonging to the directed graph $G$.

<a id="function-outdegree-grphvert"></a>
### `OutDegree(u): GrphVert -> RngIntElt`

The number of edges of the form $uv$ where $u$ is a vertex belonging to the directed graph $G$.

<a id="function-degree-grphvert-2"></a>
### `Degree(u): GrphVert -> RngIntElt`

Given a vertex $u$ belonging to the digraph $G$, return the total degree of $u$, i.e. the sum of the in–degree and out–degree for $u$.

<a id="function-alldeg-grphdir-rngintelt"></a>
### `Alldeg(G, n): GrphDir, RngIntElt -> { GrphVert}`

Given a digraph $G$, and a non–negative integer $n$, return the set of all vertices of $G$ that have total degree equal to $n$.

<a id="function-maximumindegree-grphdir"></a>
### `MaximumInDegree(G): GrphDir -> RngIntElt, GrphVert`

<a id="function-maxindeg-grphdir"></a>
### `Maxindeg(G): GrphDir -> RngIntElt, GrphVert`

The maximum indegree of the vertices of the digraph $G$. This function returns two values: the maximum indegree, and the first vertex of $G$ having that degree.

<a id="function-maximumoutdegree-grphdir"></a>
### `MaximumOutDegree(G): GrphDir -> RngIntElt, GrphVert`

<a id="function-maxoutdeg-grphdir"></a>
### `Maxoutdeg(G): GrphDir -> RngIntElt, GrphVert`

The maximum outdegree of the vertices of the digraph $G$. This function returns two values: the maximum outdegree, and the first vertex of $G$ having that degree.

<a id="function-minimumindegree-grphdir"></a>
### `MinimumInDegree(G): GrphDir -> RngIntElt, GrphVert`

<a id="function-minindeg-grphdir"></a>
### `Minindeg(G): GrphDir -> RngIntElt, GrphVert`

The minimum indegree of the vertices of the digraph $G$. This function returns two values: the minimum indegree, and the first vertex of $G$ having that degree.

<a id="function-minimumoutdegree-grphdir"></a>
### `MinimumOutDegree(G): GrphDir -> RngIntElt, GrphVert`

<a id="function-minoutdeg-grphdir"></a>
### `Minoutdeg(G): GrphDir -> RngIntElt, GrphVert`

The minimum outdegree of the vertices of the digraph $G$. This function returns two values: the minimum outdegree, and the first vertex of $G$ having that degree.

<a id="function-maximumdegree-grphdir"></a>
### `MaximumDegree(G): GrphDir -> RngIntElt, GrphVert`

<a id="function-maxdeg-grphdir"></a>
### `Maxdeg(G): GrphDir -> RngIntElt, GrphVert`

The maximum total degree of the vertices of the digraph $G$. This function returns two values: the maximum total degree, and the first vertex of $G$ having that degree.

<a id="function-minimumdegree-grphdir"></a>
### `MinimumDegree(G): GrphDir -> RngIntElt, GrphVert`

<a id="function-mindeg-grphdir"></a>
### `Mindeg(G): GrphDir -> RngIntElt, GrphVert`

The minimum total degree of the vertices of the digraph $G$. This function returns two values: the minimum total degree, and the first vertex of $G$ having that degree.

<a id="function-degreesequence-grph-2"></a>
### `DegreeSequence(G): Grph -> [ { GrphVert} ]`

Given a digraph $G$ such that the maximum degree of any vertex of $G$ is $r$, return a sequence $D$ of length $r+1$, such that $D[i]$, $1 \leq i \leq r+1$, is the number of vertices in $G$ having degree $i-1$.

<a id="function-inneighbours-grphvert"></a>
### `InNeighbours(u): GrphVert -> { GrphVert}`

<a id="function-inneighbors-grphvert"></a>
### `InNeighbors(u): GrphVert -> { GrphVert}`

Given a vertex $u$ of the digraph $G$, return the set containing all vertices $v$ such that $vu$ is an edge in the digraph, i.e. the starting points of all edges that are directed into the vertex $u$.

<a id="function-outneighbours-grphvert"></a>
### `OutNeighbours(u): GrphVert -> { GrphVert}`

<a id="function-outneighbors-grphvert"></a>
### `OutNeighbors(u): GrphVert -> { GrphVert}`

Given a vertex $u$ of the digraph $G$, return the set of vertices $v$ of $G$ such that $uv$ is an edge in the graph $G$, i.e. the set of vertices $v$ that are the end vertices of edges directed from $u$ to $v$.

<a id="function-incidentedges-grphvert-3"></a>
### `IncidentEdges(u): GrphVert -> { GrphEdge}`

The set of all edges incident with the vertex $u$.
