Mastodawn

My solution to my BP20: on the left planar graphs, that is graphs that can be embedded on the plane (on the right graphs that can't).

Lot of interesting stuff in this Bongard Problem.

Detailed contents of each box:
1: a tree;
2: complete bipartite graph K(2, 3);
3: complete graph K(4);
4: net of the cube;
5: a random planar graph;
6: Goldner-Harary graph (It's maximal planar. All its faces are bounded by three edges.
See: https://en.wikipedia.org/wiki/Goldner%E2%80%93Harary_graph );
- - - -
7: complete graph K(5);
8: complete bipartite graph K(3, 3);
9: the famous Petersen graph (that contains a minor isomorphic to the K(3,3) graph, so it's non-planar. Its crossing number is 2. Toroidal).
See:
https://en.wikipedia.org/wiki/Petersen_graph
https://en.wikipedia.org/wiki/Toroidal_graph
10: the Grötzsch graph (it is the smallest triangle-free graph with chromatic number 4, it has Book thickness 3).
See (Wolfram Mathworld shows graphs in various ways, this is quite handy):
https://mathworld.wolfram.com/GroetzschGraph.html
https://en.wikipedia.org/wiki/Gr%C3%B6tzsch_graph
11: complete bipartite graph K(3, 3) embedded on a torus, so it's toroidal (this is almost pixel art).
See:
http://www.cut-the-knot.org/do_you_know/3Utilities.shtml
12: (empty).