A double-toroidal graph is a graph with graph genus 2 (West 2000, p. 266). Planar and toroidal graphs are therefore not double-toroidal. Some known double-toroidal graphs on 10 and fewer vertices are illustrated above.
The smallest simple double-toroidal graphs are on 8 vertices, of which there are exactly 15 (all of which are connected; E. Weisstein, Sep. 10, 2018). These include the minimal graphs 
, 
, 
(Duke and Haggard 1972), the complete graph 
, the additional complete 
-partite graphs 
, 
, and 
, and the graph 
(Mohar 1989). Some of these are summarized in the following table.
| index | double-toroidal graph | reference |
| 1 |  | Duke and Haggard (1972) |
| 2 |  | Duke and Haggard (1972) |
| 4 |  | Mohar (1989) |
| 11 |  | Duke and Haggard (1972) |
| 12 |  | |
| 13 |  | |
| 14 |  | |
| 15 |  |
Duke and Haggard (1972; Harary et al. 1973) gave a criterion for the genus of all graphs on 8 and fewer vertices. Define the double-toroidal graphs
 |  |  | (1) |
 |  |  | (2) |
 |  |  | (3) |
where 
denotes 
minus the edges of 
. Then a subgraph 
of 
is double-toroidal if it contains a Kuratowski graph (i.e., is nonplanar) and contains at least one 
for 
.
." Israel J. Math. 11, 452-455, 1972.Harary, F.; Kainen, P. C.; Schwenk, A. J.; and White, A. T. "A Maximal Toroidal Graph Which Is Not a Triangulation." Math. Scand. 33, 108-112, 1973.Mohar, B. "An obstruction to Embedding Graphs in Surfaces." Disc. Math. 78, 135-142, 1989.West, D. B. "Surfaces of Higher Genus."