A subgraph consists of a subset of the vertices and a subset of the edges, with the property that for every edge in the subgraph, both its endpoints are in the subgraph. 

Two graphs G and G' are isomorphic (G@G' ) if there is a one-to-one correspondence between the vertices and one-to-one correspondence between the edges, which preserves incidence. In other words, if the edge e in G corresponds to the edge e' in G', then the endpoints of e correspond to the endpoints of e'. A graph G is plane if it is drawn in plane (or on the sphere) with no two edges crossing each other, and it is planar if it is isomorphic to a plane graph. By an embedding of a graph G we mean a drawing of G on a certain surface in which the edges do not cross. A non-planar graph can be always embedded on some surface, other then the plane (or sphere). For example, all polyhedra graphs are planar, and the graphs K5 and K3,3 are non-planar. An automorphism of a graph G is any isomorphism mapping G to itself. All automorphisms of a graph G make its automorphism group denoted as Aut(G). 

An embedding of a graph may induce a map M: the division of the unbounded surface on which the graph is embedded into disjoint simply-connected regions called faces. A face with two vertices and two edges will be called a bigonal face (or just bigon). The dual D(M) of a given map M can be constructed in the following way: in the map M you draw a vertex of D(M) in the interior of each region of M (including the exterior region), and you join them by edges, one edge of D(M) crossing each edge of M. The graph D(M) is called the dual of M. In the case of polyhedra and their corresponding graphs, you can join up the points in the interior of adjacent faces of a polyhedron P to obtain the dual polyhedron D(P). Doing this a second time gets you back to a polyhedron D(D(P)) isomorphic to P. Different planar embeddings of a planar graph G may give different dual graphs D(G), so we can have isomorphic graphs with non-isomorphic duals
 
 

PreviousContentsNext