Yeah, that's much more direct than my argument! WFL On 4/13/14, Adam P. Goucher <apgoucher@gmx.com> wrote:
Very nice discovery!
Lemma: The graph is isomorphic to the 4-by-4 toroidal grid graph.
Proof: draw the graph in the way you defined (which is on the 4-by-4 torus, but has lots of edges crossing). Then, translate all of the black vertices by (2,2) whilst preserving the positions of the white vertices. Then every vertex is connected to its four neighbours and nothing else.
--------
Corollary: (2)
Proof: Trivial.
--------
Corollary: (1)
Proof: The graph is isomorphic to the product C4 x C4 (where C4 is the cycle graph on four vertices), so is isomorphic to the product K2 x K2 x K2 x K2 (since C4 is isomorphic to K2 x K2). Consequently, the graph is isomorphic to the skeleton of the tesseract (four-dimensional hypercube).
--------
The last isomorphism I used (C4 x C4 == K2 x K2 x K2 x K2) may be familiar to any electronic engineers amongst you, on the basis that it allows Karnaugh maps to work.
Sincerely,
Adam P. Goucher
----- Original Message ----- From: Fred Lunnon Sent: 04/13/14 12:04 PM To: math-fun Subject: [math-fun] A knight's surprise?
Consider the graph whose vertices & edges represent squares & knight moves on a 4x4 chessboard tiling the torus.
(1) Find a spatial embedding with the full symmetry of the graph.
(2) Deduce that the graph can be embedded (without crossings) on the torus.
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun