The Knödel graph is a regular bipartite graph of vertex degree on nodes for even and with edges defined as follows. Label the vertices with and . Then there is an edge between and for every where , ..., (Fertin and Raspaud 2004, Clancy et al. 2019).
This class of graphs was introduced by Knödel (1975) in constructing a timeoptimal algorithm for gossiping among vertices with even , but were only formally defined by Fraigniaud and Peters (2001) (Fertin and Raspaud 2004).
Knödel graphs are Cayley and vertextransitive graphs (Fertin and Raspaud 2004). They are also Haar graphs.
Special cases are summarized in the following table.
graph  
path graph  
ladder rung graph  
square graph  
cycle graph  
Möbius ladder  
Franklin graph  
Heawood graph  
MöbiusKantor graph  
honeycomb toroidal graph  
circulant graph  
Haar graph 
The edge connectivity of is given by
(1)

and the vertex connectivity satisfies
(2)

(Fertin and Raspaud 2004).
Zheng et al. (2008) showed that the graph crossing numbers of the cubic Knödel graph is given by
(3)
 
(4)
 
(5)

for even (Clancy et al. 2019).