Suppose for contradiction that an algorithm \(A\)  solves \(\mathsf {Parity}\)  using zero-bit memory and \(O(1)\) -bit storage.
Due to the impossibility result by Cohen et al. [1]} there exists no graph exploration algorithm
using zero-bit memory and \(O(1)\) -bit storage. Hence there exists the graph \(G = (V, E, \Pi )\)  and the initial location
\(v \in V\)  such that \(A\)  decides if \(G \in {\mathsf {Parity}}\)  or not without vising all the nodes in \(G\) . Let \(u \ne v\) 
be the node not visited by the agent in the execution of \(A\) , and constructs the graph \(G^{\prime } = (V^{\prime }, E^{\prime }, \Pi ^{\prime })\) 
obtained from \(G\)  by adding one node \(u^{\prime }\)  and the edge \((u, u^{\prime })\) . Since the agent does not visit \(u\) , it cannot
distinguish \(G\)  and \(G^{\prime }\)  and thus the decision for those graphs are the same. However, the parity of \(|V|\)  and
\(|V^{\prime }|\)  are different. It is a contradiction.
