Because merging two non-adjacent vertices reduces the number of vertices in the resulting graph, the number of operations needed to represent a given graph using the operations defined by Hajós may exceed the number of vertices in [REF].
The minimum size of an expression tree describing a Hajós construction for a given graph may be significantly larger than the Hajós number of , because a shortest expression for may re-use the same graphs multiple times, an economy not permitted in an expression tree.