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 vertices connected by allowable giraffe moves are considered edges.
It is therefore a 
-leaper graph, as well as the Euclidean
distance-
graph.
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 (Jelliss 2001). For 
, the square board 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."