Classical Pseudo-Telepathy

For , consists of two isomorphic connected components. Even and odd vertices are never adjacent, thus .