## Low Degree Vertices

in tracesGraphs in some applications, such as constraint satisfaction problems described
by **saucy** have many small components with vertices of low
degree, vertices with common neighborhoods, and so on.
**saucy** handles them efficiently by a refinement
procedure tuned to
this situation plus early detection of sparse automorphisms.
**Traces** employs another method.
Recall that after the first refinement
vertices with equal colours also have equal degrees.
The target cell selector never selects cells containing vertices of
degree *0, 1, 2* or *n-1*,
and nodes whose non-trivial cells are only
of those degrees are not expanded further. Special-purpose code
then produces generators for the automorphism group fixed by
the node and, if necessary, a unique discrete colouring that refines
the node.
This technique is quite successful. However, in our opinion, graphs
of this type ought to be handled by preprocessing. For example,
sets of vertices with the same neighborhoods ought to be replaced by
single vertices with a colour that encodes the multiplicity. All
tree-like appendages, long paths of degree 2 vertices, and similar
easy subgraphs, could be efficiently factored out in this manner.