Generalized geography game graph I'm studying the Sipser textbook for my theory of complexity class. In a part of the book (i.e., Space Complexity chapter), for showing that Generalized Geography game is PSPACE-complete, the author has given an argument to model this game with TQBF problem (which is proven to be PSPACE-complete).

In a step of the argument, he has tried to construct a directed graph by using the definitions of TQBF problem (universal and existential quantifiers). What he has come up with is the following graph:



I have some questions about this graph:


I, actually, don't get it why the diamond structure has been used for showing choice possibilities of player $x_i$. Couldn't we use a simple structure like what we do on binary trees? 





How would it be if we use a hexagon shape instead of diamond for showing choices of $x_i$?
Your graph based on a binary tree would have exponential size (it would require at least $2^k$ nodes), which is probably no good for the reduction; an exponential blow-up in the size of the problem instance isn't ok.

Yes, you could use a hexagon instead of a diamond.  I don't see any advantage, but it would also provide a valid reduction.