Let us consider the following natural generalization of planar graphs.
A graph is said to be 1-planar if it can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point with other edge and any three edges do not cross at a point.
(1) Give an example of a 1-planar graph which is not planar, with a certification of non-planarity.
(2) By definition, any planar graph is 1-planar. Prove that any graph with at most six vertices is 1-planar.
(3) It is known that the chromatic number of any 1-planar graph is at most six. Give a vertex coloring of the graph illustrated in (1) with a set of colors in such a way that any two adjacent vertices are given different colors.
To show is not planar, first we note that the complete graph is planar (see Fig 1., vertices ).
Now we attempt to create by building it from it subgraph .
Each of the faces of is in the same form as each of the others.
That is, each face consists of a triangle of 3 vertices which is not incident to the 4th vertex.
So exactly where in the plane we place the 5th vertex does not matter.
W.l.o.g let us place vertex outside the triangle as shown above.
Edges , , and can be constructed without crossing an existing edge of , as indicated by dotted black lines, then it is not possible to construct edge without crossing one of , or . This is shown in dotted red.
Hence is not planar.
To prove that any graph with at most six vertices is 1-planar, we only need to prove that is 1-planar since any graph with at most six vertices is a subgraph of .
We place another vertex in the outerface of Fig.1.
Edge can be constructed by crossing , edge can be constructed by crossing and edges , , can be constructed without crossing an existing edge.
Hence the result.
