3.2 Reduced Graph
A reduced graph, $G^{\prime}=(V^{\prime},E^{\prime})$, is a data structure that supports the systematic elimination of all vertices from the graph $G=(V,E)$. The vertices of the reduced graph are denoted as $V^{\prime}(G^{\prime})$ and its edges as $E^{\prime}(G^{\prime})$. A crucial attribute of the reduced graph is efficient identification of the vertex in $V^{\prime}(G^{\prime})$ with the minimum degree.
A reduced graph supports the following operations:

Increase_degree increases the degree of vertex $v$ in $V^{\prime}(G^{\prime})$ by one.

Decrease_degree decreases the degree of vertex $v$ in $V^{\prime}(G^{\prime})$ by one.

Remove excises vertex $v$ from $$V^{\prime}(G^{\prime})$ .

In_graph tests to see whether vertex $v$ is in $V^{\prime}(G^{\prime})$.

Minimum_degree finds the vertex $v$ in $V^{\prime}(G^{\prime})$ with the smallest degree.
The topic of vertex elimination and efficient techniques for facilitating the elimination of many vertices are examined in detail in Section 8 of this document.