Mathematics Atlas

How Proof Is Made
Sign In
Text size
100%
Theme
Theorem

Gomory's Theorem

Combinatorics and Graph Theory

Gomory's theorem, in combinatorics, states that if one black square and one white square are removed from a standard 8 by 8 chessboard, the remaining 62 squares can always be tiled by 31 dominoes. The result generalizes the mutilated chessboard problem, in which two same-colored corner squares are removed and no tiling is possible because a domino always covers one square of each color, so the count of remaining squares of each color must be equal for a tiling to exist. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/

Facts
Classification
Statement Form
Existence Theorem 1
Proof Year
1973 1
Connections

Has Statement Form

Sources
1. Mutilated chessboard problem (Wikipedia)
  • Solution section
    If two squares of opposite colors are removed, then the remaining board can always be tiled with dominoes
  • Lead
    If two squares of opposite colors are removed, then the remaining board can always be tiled with dominoes; this result is Gomory's theorem, after mathematician Ralph E. Gomory, whose proof was published in 1973.
View the Source
Comments (0)
No comments yet. Be the first to share a thought.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.