Graph Theory Lessons

Answers to Lesson 3

To list all the simple graphs on four vertices we start with the null graph (no edges), then we draw the one with one edge, there are two with two edges, three with three edges, two with four edges, one with five edges, and one with six edges .

Remember that a relation R on a set D is reflexive if for all elements G of D, we have that G R G. In this case every graph is isomorphic to itself (the identity function is an isomoprhism from G to G). Therefore the relation R is reflexive.
A relation R on a set D is symmetric if for all elements G₁ and G₂ of D, . If G₁R G₂ then there is an isomorphism from G₁ to G₂. This function is one-to-one and onto so it has an inverse which is also one-to-one and onto. The function f^-1 is an isomorphism from G₂ to G₁ so G₂ R G₁. Therefore the relation R is symmetric.
A relation G on a set D is transitive if for all elements G₁ ,G₂ and G₃ of D, If G₁ R G₂and G₂ R G₃ then there is an isomorphism f from G₁ to G₂ and an isomoprhism g from G₂ to G₃. The composition of f with g is an isomorphism from G₁ to G₃. (Note that since g and f preserve adjacency so does the composition.)
A relation G on a set D is an equivalence relation if it is reflexive, symmetric, and transitive. From the discussion above, R is an equivalence relation.

e-mail: C. Mawata