 However, it is not known how to prove non-polynomial lower bounds on the Hajós number without making some complexity-theoretic assumption, and if such a bound could be proven it would also imply the existence of non-polynomial bounds on certain types of Frege system in mathematical logic.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.There exist 3-chromatic graphs for which the smallest such expression tree has exponential size.