# Be Paired or Be Square

8 white and 8 black dots are drawn on a piece of paper. Parcly and Tori take turns drawing edges, always between white and black dots not already adjacent (so the graph is always bipartite); the first player to complete a 4-cycle (square) loses.

If Parcly starts first, who has a winning strategy and how is it executed?

This puzzle is an offshoot of my (now deep) research into Zarankiewicz's problem that sprang from my genies' chess puzzles, the results of which (maximal graphs, proofs and supporting code) are being added to my Kyoto repository and the relevant OEIS sequences. My SAT-based approach to the problem is also the subject of my honours project at the National University of Singapore.

• Can you please post the answer ? Commented Oct 20, 2022 at 15:14

Second Player will always :

Win.

Winning Strategy + Reason + Explanation :

It seems that this is Zarankiewicz Problem.
Posed like this for our Puzzle:
What is the number Z(N;M) of edges in a BiPartite Graph having N nodes on each side & not having a Complete MxM Subgraph ?
Here N=8 & M=2;
According to Paper "Bipartite Ramsey numbers and Zarankiewicz numbers" [[ Wayne Goddard & Michael A.Henning & Ortrud R.Oellermann ]] this is exactly 24, which is enough to solve the Puzzle.
Every time P makes a move and T makes a move, 2 edges are consumed out of the Initial 24; Eventually, after 12+12=24 moves, P will have no edges to make a move and will have to make a Square and lose.

Comment:
With 4 Dots on each side, the Winner will be the Other Player.

• I do not think this actually works – 4-cycles don't have to use white/black vertices in the same positions on both sides. Commented Jan 23, 2022 at 20:04
• WLOG, after Parcly connects W1-B1, Tori's first move is either W1-B2 or W2-B2. All other options are equivalent to one of these. Commented Jan 23, 2022 at 20:49
• Also, regarding gender: both Parcly and Tori are female genies. Commented Jan 24, 2022 at 15:47
• I don't see how you have proved the strategy. As far as I can see, what you've stated shows that if both players cooperate, the longest possible game is 25 moves. But what if either player plays a move not in that 24-edge graph at some earlier point in the game? There are after all 64 edges to choose from. Maybe this forces a shorter game, and gives a shorter winning strategy for one of the players? Commented Jan 25, 2022 at 16:40
• @JaapScherphuis I worked out the strategy with 3 white and 3 black dots; Parcly wins by making a 5-edge tree (paths of length 2, 2, 1 starting from a central vertex), despite the maximal number of edges without making a 4-cycle being 6. Commented Jan 25, 2022 at 19:54