8.5 Querying the Reduced Graph State

A couple of reduced graph state operations are also specified in Section 8.1. Their implementations tend to fall out trivially from the data structures used for minimum degree vertex tracking.

The in_graph operator is realized by the mapping $\lambda$. If the degree of vertex $v$ is greater than zero, then $v$ is in $V^{{\prime}}(G^{{\prime}})$. Algorithm 21 formalizes this observation.

In a similar vein, the minimum_degree operation is realized by the list operation first. By definition, first($L$) gets the minimum degree vertex. Recall that the minimum degree vertex list $L$ orders the vertices by ascending degree.