Graph Isomorphism

• Read 3.1, pages 55-61
  • What is the technical definition of saying that two graphs \(G,H\) are isomorphic?
  • Do isomorphic graphs have the same order? size? degree sequence?
  • Can we have two graphs with the same order and size, but not isomorphic?
  • Show that two graphs are isomorphic if and only if their complements are isomorphic.
  • Can a graph be isomorphic to its complement?
  • Can we have two graphs with the same degree sequences, but not isomorphic? What if they are also both connected graphs?
  • List the various ways presented in this chapter with which we can test that two graphs are not isomorphic.
  • How do we define isomorphism for digraphs?
  • Work out exercise 3.13
  • Practice problems: 3.1, 3.2, 3.5, 3.8, 3.10
• Read 3.2, pages 63-65
  • Prove theorem 3.6: Isomorphism is an equivalence relation on graphs.
  • Work out exercise 3.18
  • Practice: 3.17, 3.19
  • Challenge: 3.16