AMS 301 Chapter Notes - Chapter 1.2: Aph Technological Consulting, Dey, Complete Graph
Document Summary
Two graphs g and g" are isomorphic (the same graph) if there is a. 1- to-1 correspondence between their vertices so that a pair of vertices are adjacent in g it and only if the corresponding pair of vertices are adjacent in. Useful way to think of isomorphic graphs: the first graph can be redrawn on a transparency that can be exactly superimposed over a drawing of the second graph. To be isomorphic, two graphs must have the same number of vertices and the same number of edges. A subgraph a" of a graph g is a graph formed by a subset of vertices and edges of a. If two graphs are isomorphic, then subgraphs formed by corresponding vertices and edges must be isomorphic. Subgraphs can be used to test for isomorphism. A graph with n vertices in which each vertex is adjacent to all the other vertices is called a complete graph one n vertices, denoted kn.