in two graphs and can then be defined as being homeomorphic if there is graph isomorphism from some subdivision of to some subdivision of an edge contraction removes an edge from graph and merges the two vertices previously connected by it this can lead to multiple edges between pair of verticesor self-loops connecting vertex to itself these are not allowed in simple graphsin which case some edges may need to be deleted then an undirected graph is said to be minor of another undirected graph if graph isomorphic to can be obtained from by contracting some edgesdeleting some edgesand deleting some isolated vertices planarity planar graph is graph that can be embeded in plane in other wordsit can be drawn on sheet of paper in such way that no edges cross each other this is important in applications such as printed circuit design note that it is clearly possible for planar graphs to be drawn in such way that their edges do cross each otherbut the crucial thing is that they can be transformed (by moving vertices and/or deforming the edgesinto form without any edges crossing for examplethe following three diagrams all represent the same planar graphthis graph is the fully connected graph with four verticesknown as clearly all sub-graphs of this will also be planar it is actually quite difficult to formulate general algorithms for determining whether given graph is planar for small graphsit is easy to check systematically that there are no possible vertex repositionings or edge deformations that will bring the graph into explicitly planar form two slightly larger graphs than that can be shown to be non-planar in this way are the fully connected graph with five verticesknown as and the graph with three vertices fully connected to three other verticesknown as , clearlyany larger graph that contains one of these two non-planar graphs as subgraph must also be non-planar iteslfand any subdivision or smoothing of edges will have no effect