Draw a picture on a plane. If every edge of a graph does not intersect, it is called a plane graph.

In the article of complete graph, K 4 is introduced, and here we take it as an example.

Originally, I thought that K 4 would not be a plan, and there would be two edges intersecting, but we made a deformation and drew an edge, so we drew K 4 as a plan.

In K 4, the graph is divided into four faces of the region: a, b, c and d.

There are * * * in K 4:

In order to judge whether a graph is a plan, we use

In a graph, there is a node with a degree of 2 and two edges of (V, v 1) and (V, v 2), and v 1 ≠ v 2 is called series connection.

Series reduction means deleting node V from the graph and replacing (v, v 1) and (v, v 2) with (V 1).

In the above figure, the node E is deleted through series reduction, and the edges (a, e) and (e, c) are replaced by (a, c).

If a graph G 1 can be transformed into a graph isomorphic to G 2 through series reduction (one or more steps), it is said that G 1 is homeomorphic to G 2, and vice versa.

Graph g is a planar graph if and only if g does not contain subgraphs that are homeomorphic to K 5 or k 3,3.

Kuratovsky theorem can be used to judge whether graph G is a plane graph, and an example is given in a book.

The edges (a, b), (e, f) and (g, h) in the graph are removed, and after series reduction, the graph becomes K 3,3, 3, so it is not a plane graph.

Give a plan and color each face of the plan, so that the colors of every two adjacent faces are different. How many colors does a * * * need?

This picture is painted with four colors and five sides.

Try using a more complicated chart.

This concludes the introduction of the floor plan. Thank you!