A giraffe graph is a graph formed by all possible moves of a hypothetical chess piece called a "giraffe"
which moves analogously to a knight except that it is restricted to moves that change
by one square along one axis
of the board and four squares
along the other. To form the graph, each chessboard square is considered a vertex,
and edges join vertices
related by allowable giraffe moves. It is therefore a 
-leaper graph, as well
as a Euclidean distance graph with distance
.
Giraffe graphs are bicolorable, bipartite, class 1, perfect, triangle-free, and weakly perfect.
The square (
) giraffe graph is connected
for 
.
The 
giraffe graph is traceable
for 
, 9, 10, 12, 13, 14, 15, 16, 17, 18,
19, and 20, and untraceable for 
. Waldmann reports a computer-assisted proof,
with a proof certificate checked by a separate verifier,
that the 
giraffe graph has no Hamiltonian path.
The smallest nontrivial square board allowing a closed tour for the giraffe (i.e., the giraffe
graph is Hamiltonian) is the 
, first solved by A. H. Frost in 1886 as
reported by Jelliss (2019). For 
, the square board's
giraffe graph is Hamiltonian for 
, 10, 12, 14, 16, 18, and 20.
Precomputed properties of giraffe graphs are implemented in the Wolfram Language as GraphData[
"Giraffe", 
m, n
].
1, 4
." §10.33 in Knight's Tour Notes. 2019. 
Leaper Graph on 
Has No Hamiltonian Path."