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 time-optimal 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 vertex-transitive 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öbius-Kantor 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).
-Gossip Graphs." Networks 38, 150-162,
2001.Knödel, W. "New Gossips and Telephones." Disc.
Math. 13, 95, 1975.Zheng, W.; Lin, X.; Yang, Y.; and Deng,
C. "The Crossing Number of Knödel Graph 
." Util. Math. 75, 211-224, 2008.