Kuratowaski's Graph

KURATOWSKI’S GRAPHS: For this we discuss two specific non-planar graphs, which are of fundamental importance, these are called Kuratowski’s graphs. The complete graph with 5 vertices is the first of the two graphs of Kuratowski. The second is a regular, connected graph with 6 vertices and 9 edges.

Observations
(i) Both are regular graphs
(ii) Both are non-planar graphs
(iii) Removal of one vertex or one edge makes the graph planar
(iv) (Kuratowski’s) first graph is non-planar graph with smallest number of vertices and (Kuratowski’s) second graph is non-planar graph with smallest number of edges. Thus both are simplest non-planar graphs.

The first and second graphs of Kuratowski are represented as K5 and K3, 3. The letter K being for Kuratowski (a polish mathematician).