Colouring a discretised torus
Source: Baltic Way 2018, Problem 7
November 6, 2018
combinatoricsColoringgraph theoryGraph coloring
Problem Statement
On a torus as shown all edges are colored red or blue. A coloring is good if every vertex is an endpoint of an even number of red edges. A move consists of switching the color of each of the edges of an arbitrary cell. What is the largest number of good colorings so that none of them can be converted to another by a sequence of moves?