4x4 Chromatic Sudoku Graph

Question

I was unsatisfied with existing Sudoku graphs online and my goal was to show the structure in a manner in which the regions are explicit.

Nodes which share an edge cannot have be same color. Shaded areas connote nodes in the same region; thick edges are intra-regional connections and thin edges are extra-regional connections.

Two questions:

• Are there any errors?

• Does this constitute a proof that there are only two unique, reduced forms of 4x4 Sudoku?

• If not, what additional steps do I need to take?

Answer 1

The graph looks correct - but drawing the two graphs does not, in itself, constitute a proof that these are the only two possibilities.

Presumably you want to say that there are only two forms of Sudoku up to symmetry. In this case, you want to start out by being clear up to which forms of symmetry you allow. I can think of the following:

• Permuting the colors (that is, the labels 1,2,3,4 in the grid);
• Swapping the first two rows or columns;
• Swapping the last two rows or columns;
• Swapping two $2\times 4$ or $4 \times 2$ halves of the grid.

If you want to represent the Sudoku by a graph, you want to understand what effect these have on the graphs. If it's true that there are two types, you might want to find a "canonical representative" of each type: for example, you might want to begin by fixing a particular coloring of one shaded region (though I don't think this addresses all the symmetries; you might be able to fix the coloring of a few more nodes).

Then you can make an argument that the coloring can only be completed in (2?) ways.