The hat guessing number 
of a nonempty finite simple
graph 
is the largest positive integer 
for which the following game has a guaranteed winning strategy.
One player occupies each graph vertex, and an adversary
assigns a hat from 
colors to each player. Each sees the colors in their open
graph neighborhood, but not their own. The players fix their rules in advance
and simultaneously guess their own colors without communicating. Every player must
guess, and the team wins when at least one is correct. Other players may be wrong
(Alon et al. 2020).
If 
has 
vertices, then
 |
For the upper bound, choose all hat colors independently and uniformly. Each player's chance of being correct is 
, so the expectation value
of the number of correct guesses is 
. A guaranteed win requires 
.
For the complete graph 
, 
. Label players and colors 0, 1, ..., 
. Player 
guesses the unique color that makes the sum
of all colors congruent to 
modulo 
. Exactly one player then guesses correctly (Alon et al.
2020).
All hat assignments are allowed in this definition. Restricting the adversary to proper vertex colorings gives the proper hat guessing number, which can only increase the parameter (Adriaensen et al. 2026, p. 1). Both graph games differ from the guessing-or-passing version of the hat problem, where any incorrect guess causes the team to lose.
